Qbasicnews.com
September 20, 2020, 08:49:07 PM
 Welcome, Guest. Please login or register. 1 Hour 1 Day 1 Week 1 Month Forever Login with username, password and session length
 Home Help Search Login Register
 Pages: 1 [2]
 Author Topic: Permutations  (Read 8868 times)
Agamemnus
x/ \z

Posts: 3491

 « Reply #15 on: June 23, 2006, 09:52:15 AM »

Moneo:
>Sorry, Aga, I don't understand your comments. Please explain.
Never mind the other thing... I got ahead of myself... works if you want to find the biggest number, though.

>Also, would you kindly explain how your algorithm works --- the theory first, then the details

Basically it's exactly like that recursive function above except without the ....useless... pointers.... or useless recursion...  :humm:

Pre-algorithm:

1) Start with the string.
2) Convert it to integers.
3) Sort the integers low-high.
4) Remove duplicates.

Algorithm:

What we are doing is a counter with this code:

Code:

counter(0) = counter(0) + 1
i=0

2
IF counter(i) > i+1 THEN
counter(i) = 0
i=i+1
IF i = permlength-1 THEN EXIT DO
counter(i) = counter(i) + 1
GOTO 2
END IF

The counter converts to a number that is a set of "digits" of decreasing base, for instance the size 2 number (for "abc") is counted like so:

00 = 0
01 = 1
10 = 2
11 = 3
20 = 4
21 = 5

(I'd use loops but there's already a "do...loop" and neither FB or QB support double loops, like Powerbasic, unfortunately...)

After the counter is moved up one, this code:
Code:

FOR i = 0 TO permlength-2
SWAP intperm(i), intperm(counter(permlength-2-i)+i)
NEXT i

...translates the counter to a series of swaps. The counter correlates to all succeeding positions on a permutation tree. For "abcde", the tree loops through all the different characters/values in the first spot, then all the characters in the second spot (one less choice), then all the characters in the third spot, and so on until there are only 2 characters to choose from.

Code:

FOR t = 0 TO permlength-1
MID\$(tempstring\$, t+1,1) = CHR\$(intperm(t))
NEXT t: PRINT tempstring\$; " ";

FOR i = permlength-2 TO 0 STEP -1
SWAP intperm(i), intperm(counter(permlength-2-i)+i)
NEXT i

This code prints the number and then switches it back. After this, it's looped back to the counter till the counter gets too big. (i = permlength-1)
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #16 on: June 24, 2006, 08:13:37 PM »

Aga, thanks for your explanation, but I still don't get it. I get lost right at the beginning where you say:
Code:
The counter converts to a number that is a set of "digits" of decreasing base, for instance the size 2 number (for "abc") is counted like so:

00 = 0
01 = 1
10 = 2
11 = 3
20 = 4
21 = 5

The 20 = 4 really confuses me, as does the mention of a "decreasing base". I also don't understand why "abc" is a size 2 number.

Thanks anyway.
*****
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #17 on: June 24, 2006, 09:07:13 PM »

Size 2 = 2 digits.

20 = 2, 0 = 2*2 + 0*1 = 4

If it was 3 digits it'd have the form (I think):

a, b, c = a*3*2*1 + b*2*1 + c

If 4:

a, b, c, d = a*4*3*2*1 + b*3*2*1 + c*2*1 + d
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #18 on: June 25, 2006, 08:48:25 PM »

Aga,

I appreciate your trying to enlighten me,
but I think you and I,
"went to different schools together."

*****
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #19 on: June 28, 2006, 10:28:22 PM »

Aga, Yetifoot, Cha0s,

EUREKA! I found it. An algorithm with no filter, no recursion and no sorting required. This algorithm is based on one by Dijkstra.

Here it is:
Code:

defint a-z
cls
do
print "Enter number of digits (2-9) for which to generate permutations ";
input n
loop while n<2 or n>9

dim a(1 to n)
for x=1 to n
a(x)=x
next x

DO
for x=1 to n  'Print a permutation
print a(x);
next x
print
i = n-1
while a(i) > a(i+1) : i=i-1 : wend
if i<1 then EXIT DO
j = n
while a(i) > a(j) : j=j-1 : wend
swap a(i),a(j)
r = n
s = i+1
do while r > s
swap a(r),a(s)
r=r-1
s=s+1
loop
LOOP
system

*****

EDIT: Changed 1-9 digits to 2-9.
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #20 on: June 29, 2006, 01:15:38 PM »

That's interesting.

Hard to visualize..
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #21 on: June 29, 2006, 09:37:33 PM »

Quote from: "Agamemnus"
That's interesting.

Hard to visualize..

If what you mean by "hard to visualize" is that you can't figure out how it works, well, don't feel bad, I haven't had the time to figure it out either, All I know is that it works.

Enclosed is the same algorithm with a modified front end to generate permutations of letters or numbers.
Code:

defint a-z
cls
do
print "Enter 2-9 characters for which to generate permutations ";
input ch\$
n=len(ch\$)
loop while n<2 or n>9

dim a(1 to n)
for x=1 to n
a(x)=x
next x

DO
for x=1 to n  'Print a permutation
print mid\$(ch\$,a(x),1);
next x
print
i = n-1
while a(i) > a(i+1) : i=i-1 : wend
if i<1 then EXIT DO
j = n
while a(i) > a(j) : j=j-1 : wend
swap a(i),a(j)
r = n
s = i+1
do while r > s
swap a(r),a(s)
r=r-1
s=s+1
loop
LOOP
system

*****
 Logged
 Pages: 1 [2]
Jump to: