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.

Be careful when following the masses, sometimes the m is silent.

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.

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

Be careful when following the masses, sometimes the m is silent.

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

Be careful when following the masses, sometimes the m is silent.

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

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.

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.

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

Be careful when following the masses, sometimes the m is silent.

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.

Be careful when following the masses, sometimes the m is silent.

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.

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.

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?

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.

Be careful when following the masses, sometimes the m is silent.

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?

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.

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!

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...

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

Be careful when following the masses, sometimes the m is silent.