Permutations or Cartesian Product of multidimensional sets
I've tried my darnest to come up with an algorithm that could come up with all the unique permutations of a multidimensional set of strings.
As an example, here are three lists of words:
BIG, SMALL, HUGE, TINY
brown, yellow
Cat, Dog, Parrot
I want to be able to come up with all the combinations of each of the lists, so that the answer set would contain items like:
BIG brown Dog
TINY yellow Cat
I know the total number of combinations is a factorial (in this case 4 * 2 * 3, or 24), and I know the number of repetitions of each word ("yellow" should show up 12 times in this example), but I cannot come up with a process that comes up with all the unique combinations.
I'm not expecting anyone to do my work for me, but there must be some general algorithms that I could learn from to write my own code for this.
Any ideas would be gratefully appreciated.
[926 byte] By [
Mark_Sa] at [2007-11-27 10:34:30]
Try posting what you have so far.
just a small hint:
Given just a single list of words, say
BIG, SMALL, HUGE, TINY
how would you get the compiler to print each of these words out one at a time:
BIG
SMALL
HUGE
TINY
?
Here's a hint to solve your problem in a generic way:
A = [BIG, SMALL, HUGE, TINY]
B = [brown, yellow]
C = [Cat, Dog, Parrot]
ABC
000 == BIG-brown-Cat
001 == BIG-brown-Dog
002
010
011
012
100
101
102
110
111
112
200...
201
202
210
211
212
300
301
302
310
311
312 == TINY-yellow-Parrot
column C: repetition = 1 = 0, 1, 2, 0, 1, 2, ...
column B: repetition = C.length = 3 = 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, ...
column A: repetition = B.length*C.length = 6 = 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, ... (to index 3)
Simply count to 4x2x3 == 24, for every number i in [0, 24)
take i%4 for the first list, (i/4)%2 for the second list and (i/4/2)%3 for
the last list. Note that the % operator for the last element is not needed.
kind regards,
Jos
JosAHa at 2007-7-28 18:29:17 >
> Simply count to 4x2x3 == 24, for every number i in
> [0, 24)
> take i%4 for the first list, (i/4)%2 for the second
> list and (i/4/2)%3 for
> the last list. Note that the % operator for the last
> element is not needed.
>
> kind regards,
>
> Jos
Thank you Jos: you made me look like a fool yet again today! Before your post, I made a little algorithm for fun which was spread over 3 method and ~40 lines of code in total.
Based on your observation, I wrote it in one method and ~10 lines of code.
Perhaps time to call it a day...
; )
> Thank you Jos: you made me look like a fool yet again today! Before
> your post, I made a little algorithm for fun which was spread over 3
> method and ~40 lines of code in total. Based on your observation, I
> wrote it in one method and ~10 lines of code.
> Perhaps time to call it a day...
> ; )
No need to feel ashamed; after all I am the founding father of the
SFPTBOOO (Society For Putting Things Badly Out Of Order).
kind regards,
Jos ;-)
JosAHa at 2007-7-28 18:29:17 >
By golly, it worked!
Thanks, JosAH for your suggestion, and thanks, Prometheus for your thoughts as well!
The code, listed below, is a little kludgy, but it actually works.
/*
SACRED WORDS OF WISDOM:
Simply count to 4x2x3 == 24, for every number i in [0, 24)
take i%4 for the first list, (i/4)%2 for the second list and (i/4/2)%3 for
the last list....
*/
public class CartesianProduct {
public static void main(String[] args) {
String[][] values = { { "BIG", "SMALL","HUGE", "TINY" }, {"brown", "yellow" }, {"Cat", "Dog", "Parrot" }};
int fields = values.length;
int[] counts = new int[fields];
int totalRows = 1;
for(int i=0; i<fields; i++) {
counts[i] = values[i].length;
totalRows *= counts[i];
}
for( int t = 0; t >< totalRows; t++ ) {
StringBuffer sb = new StringBuffer("");
for (int x = 0; x < fields; x++) {
int pos = t;
for (int y = 0; y < x; y++) {
pos /= counts[y];
}
int offset = pos % counts[x];
String[] members = values[x];
String member = members[offset];
if( x > 0 ) {
sb.append("\t");
}
sb.append(member);
}
System.out.println(sb.toString());
}
}
}
The counts[] array could be replaced, by values[x].length, of course.
Criminy.
There's a loop in there that should look like this:
for( int t = 0; t < totalRows; t++ ) {
That's a java forum bug, not mine.
Let's see what it looks like if I paste it between those code blocks again.
for( int t = 0; t < totalRows; t++ ) {
> Criminy.
>
> There's a loop in there that should look like this:
> for( int t = 0; t < totalRows; t++ ) {
>
> That's a java forum bug, not mine.
Yep. We're hoping this will be fixed when the next (non-crashing) forum upgrade is complete.
public class Foo {
private static void bar(String[][] arrays) {
int idx = 1;
for(int i = 0; i < arrays.length; idx *= arrays[i].length, i++);
while(idx-- > 0) {
int j = 1;
for(String[] a : arrays) {
System.out.print(a[(idx/j)%a.length]+" ");
j *= a.length;
}
System.out.println();
}
}
public static void main(String[] args) {
bar(new String[][]{
{"BIG", "SMALL", "HUGE", "TINY"},
{"brown", "yellow"},
{"Cat", "Dog", "Parrot"}
});
}
}
having problems with that post prometheuzz?
> having problems with that post prometheuzz?
Yes. There is a startling lack of design patterns in use.
;)
> having problems with that post prometheuzz?
I have no idea what's going on but since this afternoon I am not able to post text including code. I am able to post only code or only text though... Really freaky.
~: |
> > having problems with that post prometheuzz?
>
> Yes. There is a startling lack of design patterns in
> use.
>
> ;)
Design patterns? I don't do those!
; )
> > having problems with that post prometheuzz?
>
> I have no idea what's going on but since this
> afternoon I am not able to post text including code.
> I am able to post only code or only text though...
> Really freaky.
> ~: |
Anyway, the comment with post #10 was something like: "good you found the solution, and for what it's worth, here's my stab at it after Jos' observation".
Over and out.
