0

I've written a basic permutation program in C. The user types a number, and it prints all the permutations of that number.

Basically, this is how it works (the main algorithm is the one used to find the next higher permutation):

int currentPerm = toAscending(num);
int lastPerm = toDescending(num);
int counter = 1;

printf("%d", currentPerm);

while (currentPerm != lastPerm)
{
   counter++;
   currentPerm = nextHigherPerm(currentPerm);
   printf("%d", currentPerm);
}

However, when the number input includes repeated digits - duplicates - some permutations are not being generated, since they're duplicates. The counter shows a different number than it's supposed to - Instead of showing the factorial of the number of digits in the number, it shows a smaller number, of only unique permutations.

For example:

num = 1234567
counter = 5040 (!7 - all unique)

num = 1123456
counter = 2520

num = 1112345
counter = 840

I want to it to treat repeated/duplicated digits as if they were different - I don't want to generate only unique permutations - but rather generate all the permutations, regardless of whether they're repeated and duplicates of others.

Community
  • 1
  • 1
amiregelz
  • 1,833
  • 7
  • 25
  • 46
  • 1
    If you're asking how to change the code that generates the permutations, don't you think it'd be wise to show the code that does the generating? Right now you're only showing a call to a function: `nextHigherPerm(currentPerm)`. – Caleb Nov 12 '12 at 20:54
  • @Caleb I didn't include it because it's pretty long. I thought I could get some direction about what I should change/pay attention to in the `findHigherPerm` algorithm, so I will not ignore un-unique permutations. – amiregelz Nov 12 '12 at 20:54

4 Answers4

1

Uhm... why not just calculate the factorial of the length of the input string then? ;)

Nik Bougalis
  • 10,495
  • 1
  • 21
  • 37
  • I want to show all the permutations in that process, so I can't simply use !digits to calculate it. I want to also show duplicated permutations - not only unique ones - if there are ones. – amiregelz Nov 12 '12 at 20:53
  • So the simple answer is this: create a new string, with the same length as the input, and with no repeating entries. Then create a mapping between the new and old strings; generate the permutations on the new string and for each permutation map it back. e.g. If input is 76444321 create 12345678, with 1 mapping to 7, 2 mapping to 6, 3 mapping to 4 (the "first" four), 4 mapping to four (the "second" four) and so on. – Nik Bougalis Nov 12 '12 at 21:39
1

I want to it to treat repeated/duplicated digits as if they were different - I don't want to calculate only the number of unique permutations.

If the only information that nextHigherPerm() uses is the number that's passed in, you're out of luck. Consider nextHigherPerm(122). How can the function know how many versions of 122 it has already seen? Should nextHigherPerm(122) return 122 or 212? There's no way to know unless you keep track of the current state of the generator separately.

Caleb
  • 124,013
  • 19
  • 183
  • 272
1

When you have 3 letters for example ABC, you can make: ABC, ACB, BAC, BCA, CAB, CBA, 6 combinations (6!). If 2 of those letters repeat like AAB, you can make: AAB, ABA, BAA, IT IS NOT 3! so What is it? From where does it comes from? The real way to calculate it when a digit or letter is repeated is with combinations -> ( n k ) = n! / ( n! * ( n! - k! ) )

Let's make another illustrative example: AAAB, then the possible combinations are AAAB, AABA, ABAA, BAAA only four combinations, and if you calcualte them by the formula 4C3 = 4.

How is the correct procedure to generate all these lists:

  • Store the digits in an array. Example ABCD.
  • Set the 0 element of the array as the pivot element, and exclude it from the temp array. A {BCD}
  • Then as you want all the combinations (Even the repeated), move the elements of the temporal array to the right or left (However you like) until you reach the n element.

A{BCD}------------A{CDB}------------A{DBC}

  • Do the second step again but with the temp array.

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

  • Do the third step again but inside the second temp array.

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

A{B{DC}}------------A{C{BD}}------------A{D{CB}}

  • Go to the first array and move the array, BCDA, set B as pivot, and do this until you find all combinations.
Community
  • 1
  • 1
Alberto Bonsanto
  • 17,556
  • 10
  • 64
  • 93
0

Why not convert it to a string then treat your program like an anagram generator?

Jeff
  • 2,283
  • 9
  • 32
  • 50