posted 4 months ago

I have no clue how to phrase this, let's try an example

keyLength[] = [2, 3, 29, 5, 18]

For keyLength of 2 we have

keys[0] = [a, b, c]

keys[1] = [d, e, f, g]

I need to create all combinations, that is ad, ae, af, ag, bd, be, bf, bg, cd, ce, cf, cg.

For keyLength of 5 we have

keys[0] = [a, b]

keys[1] = [c, d, e]

keys[2] = [f, g]

keys[3] = [h]

keys[4] = [i, j]

I need combinations acfhi, acfhj, acghi, acghj, adfhi, adfhi, ....., beghj

Yeah, I'm not doing the example for a keyLength of 29.

I'm going to be given a keyLength. From that I will calculate they keys arrays. So, 2 questions:

1) This sounds like a Combinatorics, specifically permutations problem, but my math-fu is weak in that area and I don't wanna get better at it. I've found libraries that will get me all permutations of a string or array, but nothing that works on different arrays.

2) Any idea on an algorithm to actually implement this?

FWIW, I actually got a BA in Applied Math some 30 years ago. Haven't used it since, except when I go off on a tangent. I have occassionaly divided sin by tan, just cos.

Sorry, I'll write an apology for the above line and sin it, then get my boss to cosin it.

keyLength[] = [2, 3, 29, 5, 18]

For keyLength of 2 we have

keys[0] = [a, b, c]

keys[1] = [d, e, f, g]

I need to create all combinations, that is ad, ae, af, ag, bd, be, bf, bg, cd, ce, cf, cg.

For keyLength of 5 we have

keys[0] = [a, b]

keys[1] = [c, d, e]

keys[2] = [f, g]

keys[3] = [h]

keys[4] = [i, j]

I need combinations acfhi, acfhj, acghi, acghj, adfhi, adfhi, ....., beghj

Yeah, I'm not doing the example for a keyLength of 29.

I'm going to be given a keyLength. From that I will calculate they keys arrays. So, 2 questions:

1) This sounds like a Combinatorics, specifically permutations problem, but my math-fu is weak in that area and I don't wanna get better at it. I've found libraries that will get me all permutations of a string or array, but nothing that works on different arrays.

2) Any idea on an algorithm to actually implement this?

FWIW, I actually got a BA in Applied Math some 30 years ago. Haven't used it since, except when I go off on a tangent. I have occassionaly divided sin by tan, just cos.

Sorry, I'll write an apology for the above line and sin it, then get my boss to cosin it.

Being cremated is my last chance at having a smoking hot body.

posted 4 months ago

If you indeed need what you described, that sounds like a quite an easy task.

From what you described it looks like you have an array of arrays. You need a tool - loop, probably two along with some counters and that is it.

But perhaps there is an elegant solution with streams, which I'd like to see too if somebody would solve it.

Any idea on an algorithm to actually implement this?

If you indeed need what you described, that sounds like a quite an easy task.

From what you described it looks like you have an array of arrays. You need a tool - loop, probably two along with some counters and that is it.

But perhaps there is an elegant solution with streams, which I'd like to see too if somebody would solve it.

posted 4 months ago

Yeah, but I don't know how many arrays. For 2 arrays it's an easy nested loop, for 3 arrays it's easy, for 30 it's easy. But what if it's x? During runtime I can find x, but now do I write the nested loops I need?

Is this what lambda are for? I never did understand those things.

Is this what lambda are for? I never did understand those things.

Being cremated is my last chance at having a smoking hot body.

posted 4 months ago

I just thought of recursion. Being an embedded systems guy where anything that can blow your stack out of the water is considered evil, I haven't recursed anything in about 20 years. Trying to work out now how to do it

Liutauras Vilda wrote:

So,agandgaare considered as same combinations, or you gave a wrong sample of what you need?

`ga`is not a valid combination.

I just thought of recursion. Being an embedded systems guy where anything that can blow your stack out of the water is considered evil, I haven't recursed anything in about 20 years. Trying to work out now how to do it

Being cremated is my last chance at having a smoking hot body.

posted 4 months ago

The easiest way to do this, when you don't know the number of nested loops, is to do it recursively. The method is responsible for one nested loop, and makes a recursive call for more, as needed.

Of course, the term "easy" is relative. If you are comfortable with recursion, then yes, it should be pretty straightforward.

Henry

Jim Venolia wrote:Yeah, but I don't know how many arrays. For 2 arrays it's an easy nested loop, for 3 arrays it's easy, for 30 it's easy. But what if it's x? During runtime I can find x, but now do I write the nested loops I need?

The easiest way to do this, when you don't know the number of nested loops, is to do it recursively. The method is responsible for one nested loop, and makes a recursive call for more, as needed.

Of course, the term "easy" is relative. If you are comfortable with recursion, then yes, it should be pretty straightforward.

Henry

Piet Souris

Master Rancher

Posts: 2044

75

posted 4 months ago

Some time ago I wrote a method that created the cartesian product of any number of lists. To make that method generic (to make it work with any List, no matter what type), I had to use raw Lists. Anyway, I needed it for some assignment and haven't used it since, so it may not be the best of the set of solutions.

To create a cartesian product of lists of any type, I used the 'toString' method of every element, and used that for the cartesian product.

Well, it serves only as a demonstration of how it could be done.

The first method takes a parameter of type T and a List of type S (generic), and, using toString, creates the cartesian product T1u1, T1u2, ..., T1um:

The next method takes as parameters two Lists, of type T and S, and creates a List<String> of the cartesian product of both Lists. It does this by using the first method for every element of the first List:

And finally, the method that creates the cartesian product of any number of Lists. It does so by making a reduction of, in fact, the array of Lists:

Its use is for instance:

Output: [aA1, aA2, aA3, aA4, aA5, aB1, aB2, aB3, aB4, aB5, aC1, aC2, et cetera.

Now, I don't know if this is applicable to your problem, but maybe it gives you some idea.

And of course, a classic solution is one that uses recursion. Let us know if that is any problem.

To create a cartesian product of lists of any type, I used the 'toString' method of every element, and used that for the cartesian product.

Well, it serves only as a demonstration of how it could be done.

The first method takes a parameter of type T and a List of type S (generic), and, using toString, creates the cartesian product T1u1, T1u2, ..., T1um:

The next method takes as parameters two Lists, of type T and S, and creates a List<String> of the cartesian product of both Lists. It does this by using the first method for every element of the first List:

And finally, the method that creates the cartesian product of any number of Lists. It does so by making a reduction of, in fact, the array of Lists:

Its use is for instance:

Output: [aA1, aA2, aA3, aA4, aA5, aB1, aB2, aB3, aB4, aB5, aC1, aC2, et cetera.

Now, I don't know if this is applicable to your problem, but maybe it gives you some idea.

And of course, a classic solution is one that uses recursion. Let us know if that is any problem.

posted 4 months ago

You do. Or in other words, you don't need to. If you have a case what you showed us, that looks to me as an array of arrays, meaning only 1 outer array exists, and which holds every other possible array. To find out the number of inner arrays you can using A.length where A is an outer array (sorry for terminology inner, outter - these probably aren't official).

But I'm not fully sure I understand your problem well in details.

Jim Venolia wrote:but I don't know how many arrays.

You do. Or in other words, you don't need to. If you have a case what you showed us, that looks to me as an array of arrays, meaning only 1 outer array exists, and which holds every other possible array. To find out the number of inner arrays you can using A.length where A is an outer array (sorry for terminology inner, outter - these probably aren't official).

But I'm not fully sure I understand your problem well in details.

posted 4 months ago

Cryptopals. Turns out each column has 2-5 possible keys. I'm trying to figure how to get each permutation of possible keys. I don't wanna think about how many potential keys I'll have for a keylength of 29 or 18 (when figuring out key lengths 2, 3, 29, 5, and 18 in that order had the highest probability of being correct).

This is also why ga isn't a valid combination. a is possible key for the first column, g for the second

Liutauras Vilda wrote:But I'm not fully sure I understand your problem well in details.

Cryptopals. Turns out each column has 2-5 possible keys. I'm trying to figure how to get each permutation of possible keys. I don't wanna think about how many potential keys I'll have for a keylength of 29 or 18 (when figuring out key lengths 2, 3, 29, 5, and 18 in that order had the highest probability of being correct).

This is also why ga isn't a valid combination. a is possible key for the first column, g for the second

Being cremated is my last chance at having a smoking hot body.

posted 4 months ago

Gives the right answer but looks like I have to know ahead of time how many arrays I've got.

Recursion is the way to go, I just have to figure out how to do it.

Piet Souris wrote:Now, I don't know if this is applicable to your problem, but maybe it gives you some idea.

Gives the right answer but looks like I have to know ahead of time how many arrays I've got.

Recursion is the way to go, I just have to figure out how to do it.

Being cremated is my last chance at having a smoking hot body.

Campbell Ritchie

Marshal

Posts: 56598

172

posted 4 months ago

That is the basic form of a for loop, but you can change it as required.

A recursive solution would work too; remember that iteration and recursion are conceptually equivalent to each other.

You can write for loops the same way you write for loops for anything else. Use the standard form of a for loop:Jim Venolia wrote:. . . During runtime I can find x, but now do I write the nested loops I need? . . .

`for (int i = 0; i < something; i++) . . .`

That is the basic form of a for loop, but you can change it as required.

A recursive solution would work too; remember that iteration and recursion are conceptually equivalent to each other.

posted 4 months ago

I don't see as of now, why you need N nested loops? But I haven't tried it myself. At the moment to me looks that there are needed only 2 loops for any number of arrays.

Jim Venolia wrote:When I'm on the n'th nested for loop, what do I use for 'i'? Keep in mind every time I call this routine there will be a different number of nested for loops.

I don't see as of now, why you need N nested loops? But I haven't tried it myself. At the moment to me looks that there are needed only 2 loops for any number of arrays.

Campbell Ritchie

Marshal

Posts: 56598

172

Piet Souris

Master Rancher

Posts: 2044

75

posted 4 months ago

Well, say we have N arrays, each of size M (as OP shows, the arrays might not be equal-sized), then the cartesian product has M^N elements. If you want to get this result by using two for loops, say the first one going from 0 to M - 1, the second one going from 0 to N-1, then you have M*N steps. In these M*N steps, you need to get a result that has M^N elements. That puts a heavy demand on whatever you are doing in every step.

@Campbell:

What OP means is for instance:

I've shown a non-recursive way to get the result (using Streams, as Liutauras asked), but it is straighforward to translate it into non-Stream code (only the third method might need a little effort).

@Jim

If the number of arrays is not known upfront, then the cartesianProduct method can easily be adapted to:

private static List<String> cartesianProduct(List<List> list) {...}

Can you show us a recursive solution?

Liutauras Vilda wrote:I don't see as of now, why you need N nested loops? But I haven't tried it myself. At the moment to me looks that there are needed only 2 loops for any number of arrays.

Well, say we have N arrays, each of size M (as OP shows, the arrays might not be equal-sized), then the cartesian product has M^N elements. If you want to get this result by using two for loops, say the first one going from 0 to M - 1, the second one going from 0 to N-1, then you have M*N steps. In these M*N steps, you need to get a result that has M^N elements. That puts a heavy demand on whatever you are doing in every step.

@Campbell:

What OP means is for instance:

I've shown a non-recursive way to get the result (using Streams, as Liutauras asked), but it is straighforward to translate it into non-Stream code (only the third method might need a little effort).

@Jim

If the number of arrays is not known upfront, then the cartesianProduct method can easily be adapted to:

private static List<String> cartesianProduct(List<List> list) {...}

Can you show us a recursive solution?

posted 4 months ago

data[0] = {2, 3, 9}

data[1] = {4, 7}

data[2] = {3, 8}

With 2 nested loops, how do I go from printing 243, 248, to printing 273 and 278, followed by 343 and 348?

I've been away all day, haven't worked on this a bit.

Liutauras Vilda wrote:I don't see as of now, why you need N nested loops? But I haven't tried it myself. At the moment to me looks that there are needed only 2 loops for any number of arrays.

data[0] = {2, 3, 9}

data[1] = {4, 7}

data[2] = {3, 8}

With 2 nested loops, how do I go from printing 243, 248, to printing 273 and 278, followed by 343 and 348?

I've been away all day, haven't worked on this a bit.

Being cremated is my last chance at having a smoking hot body.

posted 4 months ago

I don't know Jim yet. Haven't got a chance to sit down and think about it well in details. I might even was too optimistic in my head about the possible solution.

But that task isn't for me so I didn't even attempted to try it out.

How about you? Have you got some code to show what have you tried?

Jim Venolia wrote:With 2 nested loops, how do I go from printing 243, 248, to printing 273 and 278, followed by 343 and 348?

I don't know Jim yet. Haven't got a chance to sit down and think about it well in details. I might even was too optimistic in my head about the possible solution.

But that task isn't for me so I didn't even attempted to try it out.

How about you? Have you got some code to show what have you tried?

Piet Souris

Master Rancher

Posts: 2044

75

posted 4 months ago

Well, since it has become pretty quiet, let me give an iterative way. Liutauras was pretty close with his two loops, it only takes one extra nested loop, no doubt he would have found it had he had time to give it a thorough look.

It looks ugly, and both the Stream way and recursive way are much nicer to look at.

Anyway, I had a problem with Jims [a, b, c], [d, e, f, g, h], et cetera. What types are a, b, ... ? And what does 'acfhi' mean and how to represent it? (see Jims opening post).

I represented 'acfhi' with List(a, c, f, h, i), eacht letter being of some type T. I therefore represent the array [a, b, c] with List<T>, and the series of arrays with List<List<T>>.

Here goes:

Use is like:

It should be straightforward to adapt this in case real arrays are needed.

It looks ugly, and both the Stream way and recursive way are much nicer to look at.

Anyway, I had a problem with Jims [a, b, c], [d, e, f, g, h], et cetera. What types are a, b, ... ? And what does 'acfhi' mean and how to represent it? (see Jims opening post).

I represented 'acfhi' with List(a, c, f, h, i), eacht letter being of some type T. I therefore represent the array [a, b, c] with List<T>, and the series of arrays with List<List<T>>.

Here goes:

Use is like:

It should be straightforward to adapt this in case real arrays are needed.

Tobias Bachert

Ranch Hand

Posts: 86

18

Piet Souris

Master Rancher

Posts: 2044

75

posted 4 months ago

hi Tobias,

that is a great idea! Never looked at it from that side, and it does indeed save a lot of memory (if the average List length = T, and we have N of 'm, then it saves about (T^N - T) / (T -1) lists.

I think it could be simplified a little. If we have index M, then that leads immediately to an index I0 of list 0, I1 of list1, et cetera, about what you do in the Tuple class, and from these indices you can directly return a List, consisting of List(0).index(I0), List(1).index(I1), et cetera.

Maybe someone who fancies performance measurements(speedwise, memorywise) could have a look?

But have a cow!

that is a great idea! Never looked at it from that side, and it does indeed save a lot of memory (if the average List length = T, and we have N of 'm, then it saves about (T^N - T) / (T -1) lists.

I think it could be simplified a little. If we have index M, then that leads immediately to an index I0 of list 0, I1 of list1, et cetera, about what you do in the Tuple class, and from these indices you can directly return a List, consisting of List(0).index(I0), List(1).index(I1), et cetera.

Maybe someone who fancies performance measurements(speedwise, memorywise) could have a look?

But have a cow!

Tobias Bachert

Ranch Hand

Posts: 86

18

posted 4 months ago

I had an eager get method at first - the disadvantage of this is that it requires at least 12+16+4*N bytes per tuple (N := number of elements in a tuple). The lazy tuple requires only 12+4+4=24 bytes (and should be easier for the JIT to inline). (Memory consumption based on 64bit w/ compressed oops.) The huge disadvantage of the lazy tuple implementation is the extremely bad cache locality -> if the tuple has to be accessed often, one can use source.get(index).toArray() (or new ArrayList<>(...) etc.) to get the same performance as with an eager tuple implementation (besides the possible intermediate garbage tuple). As long as the performance details are explicitly documented I would prefer the lazy version over an eager version.

Note: The implementation above is a very simplified implementation, i.e. #indexOf and #contains can be significantly optimized; bulk operations on a tuple can replace modulo operation and offsets array access with one multiplication and one subtraction; etc...

Note: The implementation above is a very simplified implementation, i.e. #indexOf and #contains can be significantly optimized; bulk operations on a tuple can replace modulo operation and offsets array access with one multiplication and one subtraction; etc...

posted 4 months ago

My dad's in the hospital, I'm not really working on this right now. But from a glance I think y'all are focusing on my examples, not on what I'm working with.

a) I have a 2d array[x][y]

b) The data are bytes (google cryptopals)

c) When I call foo(data), in foo I have no idea ahead of time what x nor y is.

d) If I knew what x was ahead of time this would be trivial.

e) I appreciate the help but, well, sometimes life gets in the way of hobbies

a) I have a 2d array[x][y]

b) The data are bytes (google cryptopals)

c) When I call foo(data), in foo I have no idea ahead of time what x nor y is.

d) If I knew what x was ahead of time this would be trivial.

e) I appreciate the help but, well, sometimes life gets in the way of hobbies

Being cremated is my last chance at having a smoking hot body.

It is sorta covered in the JavaRanch Style Guide. |