Algorithm for mixing a number of variables

Question

Example: I have the numbers form 1 to 10. All possible combinations, where in every combination every variable in included once without any repetition, are... well... 3628800 (10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800).

In my case, the computer has to check ALL of the combinations, instead of picking random ones. Afterwords, the system will store the needed combinations in an array. But I can't think of an algorithm and I can't find one in the internet (probably because I'm not searching the right way).

What algorithm can I use for mixing a number of variables, where all of the combinations have no repeating variables?

amit · Answer 1 · 2012-07-18T12:42:55.487

You can try a recursive approach for this.

The idea is to "guess" which number will be first, set it - and then recurse on the remaining of the array. If you do these "guesses" for all remaining elements, you get yourself all possible permutations.

This is a general case C code that prints all permutations for a given array (does not handle repeating value in the array):

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

In this approach: pre-populate an array with your numbers: 1,2,...,n - and invoke the permutation algorithm on it.

You can see it with a simple test case including the print() and swap() functions in ideone

score 1 · Accepted Answer · edited May 23 '17 at 10:09

What you are looking for is called permutations.

Wikipedia lists a few different ways:

Slow Way to get all permutations

A naive slow way involves creating a function which given an integer i, returns the ith permutation, and then just call the function N! times.

Take a look at the answer to this question here.

In-Order Way

The Lexicographic method is described as:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.

Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.

Swap a[k] with a[l].

Reverse the sequence from a[k + 1] up to and including the final element a[n].

You should sort your sequence first to get all permutations in order.

Minimal-Swapping

May be faster, but I didn't see any code examples on my quick look.

Consider the description of the Steinhaus-Johnson-Trotter algorithm.

Even's speedup is going to win the "competition". I'll just need some time to master it on a list of paper and then I'm going to try to turn it into code... Thank's a lot for the last link in your answer! — AlexSavAlexandrov, Jul 23 '12 at 15:42

score 0 · Answer 3 · answered Jul 18 '12 at 12:34

0

It seems like you are trying to shuffle your set of integers: Fisher–Yates shuffle

answered Jul 18 '12 at 12:34

Jean Logeart

52,687
11
83
118

1

I *think* he wants *all permutations* and not a *random permutation* – amit Jul 18 '12 at 12:37
You may be right. But then what's wrong with his original solution? – Jean Logeart Jul 18 '12 at 12:39
what's the original solution? As I understood - the OP did not manage to find an algorithm to get all the permutations, and that's what he is asking. Could be wrong of course. :\ – amit Jul 18 '12 at 12:40
Vote from me for a clarifying answer :) – Tim Barrass Jul 18 '12 at 12:44
1

Yes, I got it now. I leave my answer just in case somebody gets here and understands your question poorly -as I did- so that he can have an answer. – Jean Logeart Jul 18 '12 at 12:54

Algorithm for mixing a number of variables

3 Answers3

Slow Way to get all permutations

In-Order Way

Minimal-Swapping