|
|
| 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 k-permutation 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 n-queens 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 k-permutation 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 n-queens 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 k-permutation 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*(n-1)*...*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 = (n-k)!, 2*((n-k)!), 3*(n-k)!, ..., 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 k-permutation 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*(n-1)*...*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 = (n-k)!, 2*((n-k)!), 3*(n-k)!, ..., 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 k-permutation 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 Mon Jun 18, 2018 4:09 am | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
