PHP/MySQL/GWT Merge string sequence with no repetition permutation

Question

Goodday,

Currently I'm trying to merge strings together from multiple arrays and form a Permutation with no repetition. Advice?

Basically I'm using PHP/GWT/MySQL, but I welcome other language that can help doing this.. Thanks :)

Example:

array(1, 2, 3);
array(a, b, c);
array(!,@,#);
...

should get:

1)  1a!
2)  1a@
3)  1a#
4)  1b!
5)  1b@
6)  1b#
7)  1c!
8)  1c@
9)  1c#
10) 2a!
11) 2a@
12) 2a#
13) 2b!
14) 2b@
15) 2b#
16) 2c!

...

============================================================================== UPDATES

In addition, I found an alternative solution by using PHP Finding cartesian product with PHP associative arrays

From your example it looks like the first char comes from the first array, the seoncd char from the second array etc. Is that a rule that you want? — Sébastien, Oct 14 '13 at 00:20
Also you say that you want no repetition, but do you also need to use *all* possible combinations? — Sébastien, Oct 14 '13 at 00:22
hmm, i think this is kinda tricky, yes i want no repetition, and need all possible combinations but the sequence order is important, for example, array1 must be at first char, array2 must be at second char, array3 must be at third char... — Robin1990, Oct 14 '13 at 01:36

score 0 · Accepted Answer · edited May 23 '17 at 12:10

Your example output is all the tuples of the Cartesian product of your three arrays (not the permutations, which would mix the orders, too). Typically the Cartesian product is constructed with nested loops.

In Java (GWT) this could be done like this.

List<String> result = new ArrayList<String>();
for(int i=0; i<array1.length; i++) {
    for(int j=0; j<array1.length; j++) {
        for(int k=0; k<array1.length; k++) {
            result.add(array1[i]+array2[j]+array3[k]);
        }
    }
}

For the Cartesian product when the number of arrays is not hard-coded, you can build a 2D m by n array of all the indices you require; in this case m will be the product of the lengths of the arrays and n will be the number of arrays. Following your example, this array would look like

0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 0
0, 1, 1
...

Constructing this array requires some bookkeeping. I'd do it column by column. For example if you have three arrays of lengths l1, l2, and l3, then the last column is constructed from a loop index mod l3. The second column has the values from a loop index mod l2, but each value is repeated l3 times. The first column has the values mod l1, but each is repeated l2*l3 times. You could build the repeated values using a counters: one for the row number and one for the value: e.g., when the row number mod l3 is zero, increment the counter for the value, so each value gets l3 rows.

Actually, this more general question is also answered at Perfoming Cartesian product on arrays

Thanks for the swift response. of course this is a very good idea, but one more thing comes to mind. the sets of arrays are dynamic, that means i couldn't estimate how many sets are there. is there any way to improve this algorithm for that? — Robin1990, Oct 14 '13 at 01:49
Thanks for guiding me to a right path :D you're saviour of my day — Robin1990, Oct 14 '13 at 02:46

PHP/MySQL/GWT Merge string sequence with no repetition permutation

1 Answers1