• Post Reply Bookmark Topic Watch Topic
  • New Topic

How about an algorithm question  RSS feed

 
Jim Venolia
Ranch Hand
Posts: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56598
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 312
2
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!