Author 
Message 
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 


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: 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 


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: 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 


Google


Back to top 



The time now is Sun Feb 25, 2018 9:38 am  All times are GMT

