-1

If I have one array that contains items , for example

["To","Ti","Ta"]

I would like to have a function that return all permutations of appended items in array, here function would return:

[["ToTiTa"]["ToTaTi"]["TiToTa"]["TiTaTo"]["TaToTi"]["TaTiTo"]]

Could you help me please?

Pipo
  • 5,170
  • 7
  • 33
  • 66
  • Search for bubble sort algorithm to see how it works. Then go here http://stackoverflow.com/questions/14800987/javascript-sorting-by-algorithm-jquery-maybe – Jose CC Mar 22 '15 at 15:11
  • 1
    @JosephCC: What has bubble sort to do with this? The question is about permutations. – M Oehm Mar 22 '15 at 15:16
  • @JosephCC thanks but I don't want to make a buble sort, i want to make combinaisons – Pipo Mar 22 '15 at 15:16

1 Answers1

2

What you are looking for are permutations. You can create them with a recursive function.

The code below is an example. permute is the front-end function, which your code should call. permute_rec is the recursive function that builds the permutation array and swap is just a convenience function for swapping elements in an array:

function swap(array, i, j) {
    if (i != j) {
        var swap = array[i];
        array[i] = array[j];
        array[j] = swap;
    }
}

function permute_rec(res, str, array) {
    if (array.length == 0) {
        res.push(str);
    } else {
        for (var i = 0; i < array.length; i++) {
            swap(array, 0, i);
            permute_rec(res, str + array[0], array.slice(1));
            swap(array, 0, i);
        }
    }
}

function permute(array) {
    var res = [];

    permute_rec(res, "", array);
    return res;
}

console.log(permute(["A", "B", "C"]));

Edit: You can extend this code to include permutations of subarrays with this code:

function xpermute_rec(res, sub, array) {
    if (array.length == 0) {
        if (sub.length > 0) permute_rec(res, "", sub);
    } else {
        xpermute_rec(res, sub, array.slice(1));
        xpermute_rec(res, sub.concat(array[0]), array.slice(1));
    }
}

function xpermute(array) {
    var res = [];

    xpermute_rec(res, [], array);
    return res;
}

console.log(xpermute(["A", "B", "C"]));

This code creates all subarrays and then uses the original code to create the permutations. (The case of the empty array is skipped.)

M Oehm
  • 28,726
  • 3
  • 31
  • 42
  • thanks you, I did not remember name of that operation – Pipo Mar 22 '15 at 15:43
  • By the way Do you know the name of this type of permutation with no fix size?: ["A" "B", "C","AB", "BA", "AC", "CA", "CB","BC", "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"] please? – Pipo Mar 22 '15 at 15:55
  • There is probably a name for such permutations, but I don't know it. I've updated the code to create such permutations with the `xpermute` function. – M Oehm Mar 22 '15 at 16:39
  • @VivienPipo: That's "permutations of [subsets](http://stackoverflow.com/a/15649645/1048572)" – Bergi Mar 22 '15 at 17:44