Author 
Message 
DavidB science forum beginner
Joined: 01 Mar 2006
Posts: 3

Posted: Wed Mar 01, 2006 1:45 pm Post subject:
Algorithm for kpermutation of N objects



Can anyone suggest an algorithm for retrieving every subset permutation eg 3
horses out of a field of 10 in every possible combination and order?
Source code (any language) would be even better.
Thanks in advance.
DavidY. 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Mar 01, 2006 10:11 pm Post subject:
Re: Algorithm for kpermutation of N objects



DavidB wrote:
Quote:  Can anyone suggest an algorithm for retrieving every subset permutation eg 3
horses out of a field of 10 in every possible combination and order?
Source code (any language) would be even better.

There are algorithms which will find the nth permutation in
lexographical order.
((After a few moments)) I wrote a program in C last spring, where I
looked for all the permutations of n elements (of length n). The code
is:
#define prm2lex(X,Y) X = 1; \
for (ii = n; ii; ii ) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
for (jj = Y [ii], kk = 1; jj ; kk += b [jj], jj ); \
X += fact [n  ii] * kk; b [Y [ii]] = 0; }
#define lex2prm(X,Y) xp = X  1; \
for (ii = n; ii ; ii ) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
kk = xp / fact [n  ii]; \
xp %= fact [n  ii]; \
for (jj = 1; kk ; jj ++) if (b [jj]) kk ; \
while (!b [jj]) jj ++; \
Y [ii] = jj; b [jj] = 0; } \
for (jj = n; !b [jj]; jj ); Y [n] = jj;
You need an array b with n+1 elements (for scratch work), and an array
fact[] such that fact[n] = n! = n*(n1)*...*1.
prm2lex(X,Y) takes a permutation Y (the name of an array of size n) and
assigns X a number between 1 and n!., indicationg the position of that
permutation. lex2prm(X,Y) does the reverse.
If you only want to generate permutations of k objects, you could ask
for the permutations for
X = (nk)!, 2*((nk)!), 3*(nk)!, ..., n!
and only look at Y[1], ..., Y[k].
 Christopher Heckman 

Back to top 


DavidB science forum beginner
Joined: 01 Mar 2006
Posts: 3

Posted: Sat Mar 04, 2006 4:02 am Post subject:
Re: Algorithm for kpermutation of N objects



Thanks! As far as I can tell, this is an implementation of a factoradic
algorithm. I have a couple of those already.
I also have an implementation based on taking a Combination first, and the
generating Permutations of that, which works quite nicely but seems
excessively complicated.
I was really hoping for a nice simple alrogithm or code directly generating
the ordered selection that corresponds to the Excel function PERMUT(N,K).
PERMUT(10,3) = 720.
Question: a simple way to list those 720 permutations?
DavidB
"Proginoskes" <CCHeckman@gmail.com> wrote in message
news:1141251085.277233.311440@t39g2000cwt.googlegroups.com...
Quote: 
DavidB wrote:
Can anyone suggest an algorithm for retrieving every subset permutation
eg 3
horses out of a field of 10 in every possible combination and order?
Source code (any language) would be even better.
There are algorithms which will find the nth permutation in
lexographical order.
((After a few moments)) I wrote a program in C last spring, where I
looked for all the permutations of n elements (of length n). The code
is:
#define prm2lex(X,Y) X = 1; \
for (ii = n; ii; ii ) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
for (jj = Y [ii], kk = 1; jj ; kk += b [jj], jj ); \
X += fact [n  ii] * kk; b [Y [ii]] = 0; }
#define lex2prm(X,Y) xp = X  1; \
for (ii = n; ii ; ii ) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
kk = xp / fact [n  ii]; \
xp %= fact [n  ii]; \
for (jj = 1; kk ; jj ++) if (b [jj]) kk ; \
while (!b [jj]) jj ++; \
Y [ii] = jj; b [jj] = 0; } \
for (jj = n; !b [jj]; jj ); Y [n] = jj;
You need an array b with n+1 elements (for scratch work), and an array
fact[] such that fact[n] = n! = n*(n1)*...*1.
prm2lex(X,Y) takes a permutation Y (the name of an array of size n) and
assigns X a number between 1 and n!., indicationg the position of that
permutation. lex2prm(X,Y) does the reverse.
If you only want to generate permutations of k objects, you could ask
for the permutations for
X = (nk)!, 2*((nk)!), 3*(nk)!, ..., n!
and only look at Y[1], ..., Y[k].
 Christopher Heckman



Back to top 


Doug Quale science forum beginner
Joined: 04 Mar 2006
Posts: 2

Posted: Sat Mar 04, 2006 9:54 am Post subject:
Re: Algorithm for kpermutation of N objects



"DavidB" <davidb@hurkle.nospam.com> writes:
Quote:  I was really hoping for a nice simple alrogithm or code directly generating
the ordered selection that corresponds to the Excel function PERMUT(N,K).
PERMUT(10,3) = 720.
Question: a simple way to list those 720 permutations?

If all you need to do is handle a small, fixed k, the simplest
implementation uses k nested loops. In this example, three:
n = 10
for i from 1 to n
for j from 1 to n
if j == i then next j
for k from 1 to n
if k == i or k == j then next k
visit (i, j, k)
If k is variable rather than fixed a simple backtracking algorithm
will work.
Many solutions to the nqueens problem have the same structure, since
often they generate all permutations of {1, ..., n} and test for the
required properties. 

Back to top 


DavidB science forum beginner
Joined: 01 Mar 2006
Posts: 3

Posted: Wed Mar 08, 2006 2:19 pm Post subject:
Re: Algorithm for kpermutation of N objects



Thanks, Doug.
Yes, it's variable. I considered using an algorithm for variable nested
loops out of Ian Oliver's Programming Classics, but I really prefer an API
with "Setup" and "Next" functions, rather than writing my code inside the
loops.
I finished up with a Permutation of a Combination, both from the same book.
I still feel there must be a good answer to this one  another time.
DavidB
"Doug Quale" <quale1@charter.net> wrote in message
news:877j7a8rhd.fsf@shiva.mad.wi.charter.com...
Quote:  "DavidB" <davidb@hurkle.nospam.com> writes:
I was really hoping for a nice simple alrogithm or code directly
generating
the ordered selection that corresponds to the Excel function PERMUT(N,K).
PERMUT(10,3) = 720.
Question: a simple way to list those 720 permutations?
If all you need to do is handle a small, fixed k, the simplest
implementation uses k nested loops. In this example, three:
n = 10
for i from 1 to n
for j from 1 to n
if j == i then next j
for k from 1 to n
if k == i or k == j then next k
visit (i, j, k)
If k is variable rather than fixed a simple backtracking algorithm
will work.
Many solutions to the nqueens problem have the same structure, since
often they generate all permutations of {1, ..., n} and test for the
required properties. 


Back to top 


Google


Back to top 



The time now is Mon Oct 23, 2017 2:21 am  All times are GMT

