Re: String Permutation

"Richard Heathfield" <rjh@xxxxxxxxxxxxxxx> wrote in message
news:08mdnfdfWeQ8G_vbnZ2dnUVZ8qTinZ2d@xxxxxxxxx

<snip>
Well, it might be. For example, let's say you have the letters ABC,
having the usual relation to each other. Consider this list of
arrangements of the letters:

ABC
ACB
BAC
BCA
CAB
CBA

This arrangement, clearly, is a sorted list of all possible permutations
of those letters.

Okay, let's forget for a moment that we have this list. Given ONLY the
letters A, B, C and the implicit ordering relationship between them,
and given a number K, can we find the Kth permutation WITHOUT
generating the whole list, sorting it, and peeking at the Kth element?

That appears to me to be a reasonable question. Here's another - can we
establish K for a given permutation? That is, without our crib list
(above), and given a given permutation, can we calculate what value
that permutation would have occupied in our list?
....
I haven't actually done the research, but I know we can cover N
different permutations in N calls, so it wouldn't surprise me if the
answer to both questions is indeed "yes".

The answer to both parts is yes!

In the example you provide, consider each element (A, B, C) representing a
digit (0..2) in this case. The significance of the position of the digit
(in the sequence) is based on the factorial of the position (aka the
permutations of the digits to the right).

However, as you go through a given sequence from left to right, you need to
reduce the corresponding 'value' for any element greater than the element
you have just considered.

To illustrate, consider the sequence BCA, this is represented by [1][2][0]

So,
1) Consider [1], its 'significance is 2!, so our running 'value' is 1*2!
=> 2
2) Reduce remaining 'digits' greater than [1] => [1][0]
3) Evaluating the next 'digit' gives 1* 1! => 1,
4) Adding this to the total => 2+1 => 3.
You can repeat the process for the last digit, but it will always be zero -
so you can omit it!

This corresponds to the 'crib sheet' (provided you start counting from 0).

As a more interesting example consider BDAC;
=> [1][3][0][2]

1*3! => 6, [2][0][1], value = 6
2*2! => 4, [0][1], value = 10
0*1! => 0, [0], value = 10

So BDAC is at position 10 in the ordered permutations of ABCD (if we start
counting at 0).

Of course, there are various ways of optimizing this approach! I think
doing digit value reduction first, and rolling up the factorial calculation
with the value calculation looks quite good.

e.g.
[1][3][0][2]
Consider the first digit [1], reduce all following values that are greater
than it.
[1][2][0][1]
Now consider the second digit [2] in the same way.
[1][2][0][1]
Now consider the third digit [0] in the same way.
[1][2][0][0]
Nothing to do for the last digit.

Calculate the value as
(([1]*3 + [2])*2 + [0])*1 + [0] => 10.


Now let's find out what is at position 15 in the ordered permutations of
ABCD.

Our map of digit values starts out:
3 2 1 0
D C B A

The significance of the first digit is 3!.

So 15/3! = 2 remaining 3 => the first character is C
Now we have
2 1 0
D B A
And 3/2! = 1 remaining 1 => the second character is B
1 0
D A
1/1! = 1 remaining 0 => the third character is D
leaving A at the end.

So CBDA is at position 15!

You can do a similar optimization as above - left as an exercise for those
who are interested.

HTH
--
Stuart


.

Relevant Pages

  • Re: WHAT COMBINATION OF A SET OF NUMBERS COMES CLOSEST TO A FIXED
    ... I modified a copy Myrna Larson's code (for permutations and combinations) to ... calculate the nearest set of values to 100,000 for a subset of 6 five digit ... >> lowest possible 6 digit number. ... >> HTH, ...
    (microsoft.public.excel.programming)
  • Re: String Permutation
    ... For example, let's say you have the letters ABC, ... having the usual relation to each other. ... arrangements of the letters: ... Only permutations of sets have no ordering and, of course, sets have no ...
    (comp.programming)
  • Re: Enigma 1405 - Digitally divided
    ... It's a better approach than I used, but there are a few slips 'tween ... {odd, odd, odd, 8} ... Therefore it cannot co-exist with an even digit, meaning is out. ... All 6 permutations of 5 work, as shown in list 3. ...
    (rec.puzzles)
  • Re: Number possibilities
    ... how many different 4 digit combos i will have? ... 1234 and 4321 are different Permutations. ... print 'the Combinations without Replacement' ...
    (sci.math)
  • Re: Generating all combinations
    ... Permutations and combinations are arrangements of a single set. ... Cartesian product, on the other hand, are the arrangements of multiple ... letters before putting them into the envelopes. ...
    (comp.lang.python)