1

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.

pmr
  • 58,701
  • 10
  • 113
  • 156
gmaster
  • 692
  • 1
  • 10
  • 27
  • Sorry, I don't understand much your question. If you give a number 20, so the answer something would be: 20,02,220,200,000,....222222,000000 ? – hqt Feb 23 '12 at 15:19
  • To clarify, I am saying that I want to generate every possible combination of a group of numbers. If the given number was 1234, I need to generate 1234, 1243, 1432, 4213, etc. until every possible combination has been generated. – gmaster Feb 23 '12 at 15:25
  • See the similar thread - **[Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n)**. – Dmytro Chyzhykov Feb 23 '12 at 15:32
  • I assume you want to ignore duplicates e.g. 222 could be 1 or 6 combinations the same. – Peter Lawrey Feb 23 '12 at 15:46

2 Answers2

5

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 ?

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
  • For a 1 digit number, you wouldn't have to change anything. I'm sorry, but I have absolutely no idea what you're going for. I thought using 2 for loops, but that would not generate every possible term. – gmaster Feb 23 '12 at 15:22
  • @gmaster: this is YOUR homework so I'm only giving hints. Get a pencil and paper. Write on it any single digit number. Now think of a 2 digit number which includes the first digit. Now write down a copy of the first digit, put the 2nd digit next to it and you have one permutation. Now, how else can you put the 2nd digit next to the 1st for another permutation ? When you have figured it out on paper turn your method into code. But until you have figured it out, forget your premature code. – High Performance Mark Feb 23 '12 at 15:25
  • 1
    Honestly, for help with homework, this is a good and fair hint :) – ArjunShankar Feb 23 '12 at 15:57
  • 1
    @gmaster He's trying to help you with recursion, theres another hint. – Kevin Feb 23 '12 at 16:58
2

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' :)

ArjunShankar
  • 23,020
  • 5
  • 61
  • 83
  • What do you mean "prepend firstDigit into each element of 'subPermutations'"? I don't see how this would get every possible permutation. – gmaster Feb 23 '12 at 15:42
  • prepend means add at the beginning. I didn't see how I could explain this in a comment, and I didn't consider it worth putting it in the answer. So read the above pastepin URL (which is set to expire in 1 month) – ArjunShankar Feb 23 '12 at 15:56