Calculating Permutations

I recently came across this problem:

Find the only 10 digit number which uses each of the digits 0 – 9 and has the following property: The number formed by the first n digits should be divisible by n. That is

  • The first digit should be divisible by 1
  • The number formed by the first 2 digits should be divisible by 2.
  • The number formed by the first 3 digits should be divisible by 3.
  • And so on until the number formed by the first 10 digits should be divisible by 10.

I am not going to attempt to solve this in today’s post. Rather, it got me thinking about permutations and how to generate them using computers.

An exhaustive search of all the possible answers to this problem would entail generating a list of all possible 10 digit numbers consisting of the digits 0-9. Obviously the first digit can be any of the 10. The second digit would need to selected from the remaining 9 digits, and so on. Therefore the total count of possible numbers would be:
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

This is usually written as 10! (pronounced factorial 10). In general the factorial of a number is the result of multiplying it and all lower integers down to 1.

10! = 3628800, so we would need to calculate all these permutations to check against the conditions of the problem (yes, I know that there are various optimizations we can use to reduce the number of candidates; I will possibly come back to them in another post).

So, how do we calculate all the possible permutations? A quick search on the Internet revealed this algorithm:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

  1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
  2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
  3. Swap s[i] with s[j].
  4. Reverse all the order of all of the elements after index i.

In our case we start with string ‘0123456789’. Applying step 1 we find that the 8 is less than the 9, so we set i = 9 (the 9th digit). Applying step 2 we can set j = 10. In step 3 we swap these two digits. At step 4 we need to reverse the digits after the 9th digit, which in this case is the single digit 8. The result of these steps is the string ‘0123456798’.

We then repeat these steps with the new string  ‘0123456798’. Applying step 1 we find that the 7  is less than the 9, so we set i = 8 (the 8th digit). Applying step 2 we can set j = 10. In step 3 we swap these two digits. At step 4 we need to reverse the digits after the 8th digit, which is now the string ’97’.  Reversing this gives us ’79’.  The result of these steps is the string ‘0123456879’.

This is a Delphi implementation of this algorithm:

function TfrmMain.GetNextPerm(s: string): string;
var
    i, j, n : integer;
    t : Char;
    tempString : string;
begin
    result := s;
   
    //step 1
    i := length(s);
    for n := length(s) - 1 downto 1 do begin
      i := n;
      if (s[i] < s[i + 1]) then break;
    end;
    if (s[i] >= s[i + 1]) then exit;   //already at last permutation

    //step 2
    j := length(s);
    for n := length(s) downto 2 do begin
      j := n;
      if (s[j] > s[i]) then break;
    end;

    //step 3
    t := s[i];
    s[i] := s[j];
    s[j] := t;

    //step 4
    tempString := '';
    for n := length(s) downto i + 1 do
      tempString := tempString + copy(s, n, 1);
    if (tempString <> '') then s := copy(s, 1, i) + tempString;

    result := s;
end;

We can use the following code to generate all the required permutations for our problem:

procedure TfrmMain.CheckPerms;
var
  s, t: string;
  i: integer;
begin
  i := 1;
  s := '0123456789';
t := GetNextPerm(s);
  while (s <> t) do begin
    inc(i);
    s := t;
t := GetNextPerm(s);
  end;
ShowMessage(IntToStr(i));
end;

On my PC this displays the result 3628800 in under 2.5 seconds.

We will return to the actual problem in another post.

Tags: ,

2 Responses to “Calculating Permutations”

  1. at work says:

    Summer thanks…

    hello appreciate your article have a browse of mine…

  2. My Homepage says:

    … [Trackback]…

    […] Find More Informations here: nimusi.net/blog/2010/08/calculating-permutations/ […]…