CODEWITHSUNDEEP
algorithmvariableslanguage-agnosticcombinations
AlexSavAlexandrov
AlexSavAlexandrov

Reputation: 873

Algorithm for mixing a number of variables

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?

Upvotes: 0

Views: 635

Answers (3)

Xantix
Xantix

Reputation: 3331

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.

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

  2. 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.

  3. Swap a[k] with a[l].

  4. 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.

Upvotes: 1

amit
amit

Reputation: 178461

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

Upvotes: 5

Jean Logeart
Jean Logeart

Reputation: 53829

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

Upvotes: 0

Related Questions