programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Ranch Hand
Posts: 421
2
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]

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.

Sheriff
Posts: 5718
393

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.

So, ag and ga are considered as same combinations, or you gave a wrong sample of what you need?

Liutauras Vilda
Sheriff
Posts: 5718
393

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.

Jim Venolia
Ranch Hand
Posts: 421
2
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.

Jim Venolia
Ranch Hand
Posts: 421
2

Liutauras Vilda wrote:
So, ag and ga are 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

author
Sheriff
Posts: 23513
138

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

Master Rancher
Posts: 2658
91
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.

Liutauras Vilda
Sheriff
Posts: 5718
393

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.

Jim Venolia
Ranch Hand
Posts: 421
2

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

Jim Venolia
Ranch Hand
Posts: 421
2

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.

Marshal
Posts: 59147
180

Jim Venolia wrote:. . . During runtime I can find x, but now do I write the nested loops I need? . . .

You can write for loops the same way you write for loops for anything else. Use the standard form of a for loop:
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
Ranch Hand
Posts: 421
2
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.

Liutauras Vilda
Sheriff
Posts: 5718
393

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: 59147
180

Jim Venolia wrote:. . . what do I use for 'i'?

j k l m n
i1 i2 i3 i4

. . . a different number of nested for loops.

Liutauras has already shown you that isn't correct.

Piet Souris
Master Rancher
Posts: 2658
91

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
Sheriff
Posts: 5718
393

Piet Souris wrote:I've shown a non-recursive way to get the result using Streams

Somehow I did not see this your post, probably was in a progress of writing mine and just missed. I'll analyse it - thanks!

Jim Venolia
Ranch Hand
Posts: 421
2

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.

Liutauras Vilda
Sheriff
Posts: 5718
393

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: 2658
91
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.

Ranch Hand
Posts: 86
18
I would use a wrapper implementation that creates the combinations lazily as storing all combinations might require quite a bit memory. A possible skeletal implementation:

Piet Souris
Master Rancher
Posts: 2658
91
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!

Tobias Bachert
Ranch Hand
Posts: 86
18
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...

Jim Venolia
Ranch Hand
Posts: 421
2
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

Jim Venolia
Ranch Hand
Posts: 421
2
Got it:

I'll modify it to build a list instead of printing out each key, that should be simple.

Piet, I'll try to understand your use of Streams soon.