Finding serial number of combination in a permutation
Johnynl
For example if we have to choose three numbers out of eight, the number of possible combinations is 56, starting from '123', '124', '125'... and ending with '678'. In such an order, serial combination number e.g. 36 is combination '278', 47 is '456' and the last serial 56 is '678'.
If I want to know what serial is the combination e.g. '267', what would be the best logical or algorithmical way of solving this, regardless of base system (in this case base 8).
Note that the numbers in a combination are always in ascending order e.g. '236', '458' etc, so something like '317' is not possible.
matt271...@yahoo.co.uk
Suppose you're choosing k from n, and the numbers given are x(1),
x(2), ... x(k). In your example k = 3, n = 8, and, for example, for
the combination "267" we have x(1) = 2, x(2) = 6, x(3) = 7. Then the
sequence number that you want is:
C(n, k) - sum_j=1^k C(n - x(j), k - j + 1)
where C(x, y) denotes a binomial coefficient, and we take C(x, y) = 0
if y > x.
Johnynl
Unfortunately I am not a mathematician, so your formula looks a bit like Voodoo to me.
Would you be so kind and show me on an example, how should I substitute the numbers?
Lets say we need 4 out of 9 numbers (1 to 9) and I want to find out sequence numbered 33.
Thank you in advance.
matt271...@yahoo.co.uk
That's a different question. Originally you said "If I want to know
what serial is the combination e.g. '267'...", which means you are
given the combination and want to find the corresponding sequence
(i.e. serial) number. That was the question I answered. Now you seem
to be saying that you are given the sequence number (e.g. 33) and you
want the corresponding combination. Which way round are you actually
trying to do it?
Johnynl
matt271...@yahoo.co.uk
> You're right, I need both answers, so both examples are welcome.
BTW, many people find these threads easier to follow if you post your
message as a reply to the message you are responding to (rather than
just posting it in a detached way somewhere in the thread), and if you
include, above your message, sufficient context from the message you
are replying to.
1) Convert combination to sequence number.
Following your original example of choosing 3 numbers from 1 to 8, we
have n = 8, k = 3. Suppose the given combination is "158", then x(1) =
1, x(2) = 5, x(3) = 8. Repeating the formula I gave earlier, the
corresponding sequence number is:
C(n, k) - sum_j=1^k C(n - x(j), k - j + 1)
C(x, y) ("x choose y") is a binomial coefficient, equal to the number
of different ways of choosing x items from y, disregarding order. It
is calculated as C(x, y) = x!/(y!*(x - y)!), where x! ("factorial x")
is equal to 1*2*3*4 ... *x. By definition 0! = 1, and for these
purposes C(x, y) is defined as 0 when y > x.
"sum_j=1^k" means sum over j = 1 to j = k. So the formula evaluates as
C(8, 3) - (C(8 - x(1), 3 - 1 + 1) + C(8 - x(2), 3 - 2 + 1) + C(8 -
x(3), 3 - 3 + 1))
= C(8, 3) - (C(7, 3) + C(3, 2) + C(0, 1))
= 56 - (35 + 3 + 0)
= 18
2) Convert sequence number to combination.
The following procedure does this conversion. I wouldn't be certain
it's the most efficient way of doing it, but at least it isn't grossly
inefficient:
x(0) = 0
For i = 1 To k
m = binomial(n - x(i - 1) - 1, k - i)
j = 1
While m < s
s = s - m
m = m * (n - x(i - 1) - j - k + i) / (n - x(i - 1) - j)
j = j + 1
Wend
x(i) = x(i - 1) + j
Next
On entry, k and n are as before, and s is a copy of the sequence
number (I say "copy of" because the routine changes the value of s as
it goes along). The corresponding combination is placed in x(1), x(2),
x(3) ... x(k). At the start x(0) is set to zero just as a convenience
so the code can be written more compactly. i, j and m are local work
variables. The "binomial" function (what I denoted "C" before)
calculates a binomial coefficient as defined above.
matt271...@yahoo.co.uk
[snip]
> C(x, y) ("x choose y") is a binomial coefficient, equal to the number
> of different ways of choosing x items from y, disregarding order. It
> is calculated as C(x, y) = x!/(y!*(x - y)!), where x! ("factorial x")
> is equal to 1*2*3*4 ... *x. By definition 0! = 1, and for these
> purposes C(x, y) is defined as 0 when y > x.
If you're unfamiliar with computing binomial coefficients then, by
coincidence, there's a thread at http://groups.google.com/group/sci.math/browse_frm/thread/0dc507b2dbacbda1
which may be of interest.
Johnynl
>
> BTW, many people find these threads easier to follow
> if you post your
> message as a reply to the message you are responding
> to (rather than
> just posting it in a detached way somewhere in the
> thread)
Well, I posted simply using the button "Reply to this topic" and I have no problem seeing the sorted topic in my browser.
Do you use newsreader? Maybe its something with your 'view' settings there.
This time I tried to reply directly to the last message.
Thanks again.
matt271...@yahoo.co.uk
The thing is that some people using some types of newsreader software
only see "disembodied" messages (as I gather from the numerous
complaints on this topic over the years), so without any context it's
impossible for them to figure out what, say "You're right, I need
both answers, so both examples are welcome." refers to. Even if you're
using Google, or something else sensible that shows the thread as a
tree, it can still be difficult in very long threads to associate
replies with messages when no context is included in the reply.