CODEWITHSUNDEEP
javaarrayssorting
gmaster
gmaster

Reputation: 692

Generate all unique permutations

I am working on a problem in which I am given a number and need to find every possible permutation of the digits in that number. For example, if I am given 20, the answer would be: 20 and 02. I know that there are n! possible permutations, and I have divided up the numbers so that each digit is an element in an array. My question is: How can I loop through this array to generate every possible combination of a number that is at least 2 digits long but no more than 6.

Upvotes: 1

Views: 6913

Answers (2)

ArjunShankar
ArjunShankar

Reputation: 23680

Say the n individual digits are in an array of length n. Then the problem of generating the permutations boils down to:

  1. Choosing one of the n digits as the first digit to print.
  2. Permuting the remaining n-1 digits.

A recursion.

The pseudocode for such a recursive function permute would be something like:

List permute (Array digits)
{
  List permutations = /* initialize an empty list */

  for (i=0; i<n; i++)
    {
      firstDigit = digit[i];
      Array otherDigits = /* array containing all digits except firstDigit.  */
      List subPermutations = permute(otherDigits);
      /* prepend firstDigit into each element of 'subPermutations' */
      /* add all elements of 'subPermutations' to the list 'permutations' */
    }
  return permutations;
}

Then simply call permute and print out the list, or do whatever else with it.

EDIT: You also need to handle the edge case of permuteing 1 digit.

I think this is already too much information for 'homework' :)

Upvotes: 2

High Performance Mark
High Performance Mark

Reputation: 78324

Hint:

How would you solve this problem for a 1-digit number ?

Now, how would you solve this problem, given that you have the answer to the previous question, for a 2-digit number ?

Upvotes: 5

Related Questions