Create all unique permutations

Question

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

Answer 1

Say n single digits in an array of length n . Then the task of generating permutations is reduced to:

• Select one of the digits n as the first digit to print. A.
• Transfer the remaining n-1 digits.

Recursion.

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

 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 just call permute and print the list, or do something else with it.

EDIT: you also need to process the edge with a 1-digit permute edge.

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

Answer 2

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?