0

I'm looking for a good way to make a program for this problem:

First an array with string values is given:

    var array1 = ["a", "b", "c", "d"]

Next I would like to store every possible combination(order) of the string values in new arrays

ex: 

    combo1 = ["a", "b", "d", "c"]
    combo2 = ["a", "c", "b", "d"]
    combo3 = [...etc.]

The program needs to be able to do this with big array's as well. With for example up to 20 items in the first array (array1). So it needs to do all the work of creating the 'combo array's' automatically with a function.

What would be a good way to tackle this problem? Preferably with JavaScript, but I'm open to hear about it in out languages.

As you may have guessed, I am a fairly beginner when it comes to programming. I have got the basics down and am now trying to wright a program for a project. Please help and thank you in advance!

zx81
  • 41,100
  • 9
  • 89
  • 105
Sergethelight
  • 1
  • 1
  • 2
    have you come up with any algorithm for this ? – exexzian Dec 16 '13 at 11:48
  • 1
    These are called permutations. If you try calculate permutations of large lists (20 items, for example), you are probably going to run out of memory. A list of 20 items has 20 factorial permutations.... that's 2.432902 x 10^18 or over two-million-trillion different combinations. – sbking Dec 16 '13 at 11:50
  • An alternative to storing the results, would be to have a callback that you pass a permutation to every time you generate a new one. That way you avoid the memory requirements of storing all the results. However, you're then only shifting the problem from one of memory limits, to one of execution time. – SpoonMeiser Dec 16 '13 at 11:57
  • @SpoonMeiser I have written an answer on that idea some time ago: http://stackoverflow.com/a/18874247/1669279 You're right that the inherent exponential complexity of the problem means that the execution time will be too great for many items. 20 is probably too many. – Tibos Dec 16 '13 at 12:02
  • I overlooked the memory problem. So for now I will keep it at 5 items which should return 120 results if I am correct. I haven't come up with a working algorithm yet, but my first instinct was using for loops. – Sergethelight Dec 16 '13 at 12:04
  • I'll have a look at the links. Thank you – Sergethelight Dec 16 '13 at 12:10

1 Answers1

0

In haskell you could use permutations

 permutations "abc" == ["abc","bac","cba","bca","cab","acb"]

In JavaScript you need to write the permutations function yourself:

function permutations(list) {
    if (list.length <= 1)
        return list.slice();

    var result = []
      , i = 0
      , resultRest
      , current
      , rest
      , j;
    for(; i<list.length; i++) {
        rest = list.slice(); // make a copy of list
        current = rest.splice(i, 1);
        permutationsRest = permutations(rest);
        for(j=0; j<permutationsRest.length; j++) {
            result.push(current.concat(permutationsRest[j]));
        }
   }
   return result;
}
permutations(['a', 'b', 'c'])
> [ [ 'a', 'b', 'c' ],
    [ 'a', 'c', 'b' ],
    [ 'b', 'a', 'c' ],
    [ 'b', 'c', 'a' ],
    [ 'c', 'a', 'b' ],
    [ 'c', 'b', 'a' ] ]

However, if your input is big this will take a while. Maybe you should think about another approach.

Lasse
  • 411
  • 4
  • 15
  • The code works of course, but how can I get each permutation in it's own array? Ex: var Arr1 = [ 'a', 'b', 'c' ] , var Arr2 = [ 'a', 'c', 'b' ] ? Could you help me out wit some additional code for this? – Sergethelight Dec 18 '13 at 21:32
  • There's one thing you could do in a browser environment: `for(var i=0; i – Lasse Dec 18 '13 at 22:54