Qbasicnews.com
January 26, 2020, 02:03:18 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: 1 [2]
  Print  
Author Topic: Permutations  (Read 8095 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." Shocked

*****
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]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!