generating all permutations

[tsh73]

en.wikipedia.org/wiki/Heap's_algorithm
(tweaked until worked [or seems to.])
Said to be fastest
Recursive version

EDIT I just checked it against my older code - likely along 
en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
and this one 70% faster.

---

EDIT from 35 to 21 - how's that?

(35-21)/21 66(%)

(35-21)/35 40(%)

So is it 66% faster or 40%?

---

INDEED. Who might think.

'https://en.wikipedia.org/wiki/Heap's_algorithm

global N
N=3
N=4
N=6 '63
N=7 '313
N=8 '2469
N=9 '22109


dim A(N)
for i = 1 to N: A(i)=i: next
t0=time$("ms")
call generate N
t1=time$("ms")
print "Time taken ";t1-t0

end

sub generate n
   if n = 1 then
         'call outputA
   else
       for i = 1 to n - 1
           call generate n - 1
           if n mod 2 = 0 then
               tmp=A(i):A(i)=A(n):A(n)=tmp
           else
               tmp=A(1):A(1)=A(n):A(n)=tmp
           end if
       next
       call generate n - 1
   end if
end sub

sub outputA
   for i = 1 to N
       print A(i);
   next
   print
end sub



[tsh73]

Non-recursive version. along Wikipedia article
Somehow works slower for me ()

sub generateNoRec n
   dim c(n)
   for i = 1 to n: c(i)=1: next
   'call outputA

   i=1
   while i <=n
       if c(i)<i then
           if i mod 2 = 1 then
               tmp=A(1):A(1)=A(i):A(i)=tmp
           else
               tmp=A(c(i)):A(c(i))=A(i):A(i)=tmp
           end if
           'call outputA
           c(i)=c(i)+1
           i=1
       else
           c(i)=1
           i=i+1
       end if
   wend
end sub


[B+]

Hi tsh73,

Oh man we did this back in 2016!

Here is a reminder and mod for timed test:
'ordered permutations forJB v1.01 [B+=MGA] 2016-07-21 first posted
'recursive ordered permutations
'if 1st element < 2nd element < 3rd element... then list acsends

' 2018-07-31 modified for timed test = 'mod
' mod or vice versa!
' mod if 1st element > 2nd element > 3rd element... then list descends

s$="123456789"
s$="abcdefghi" 'Time taken 19861
s$="tsh73"

global ls, index
ls = len(s$) : index = 0
dim c$(ls)
t0 = time$("ms")   'mod
call orderperm s$
t1=time$("ms")     'mod
print "Time taken ";t1-t0   'mod

sub orderperm r$
   scan
   if len(r$) = 0 then
       'mod comment out for timed test,
       'mod comment in to see results
       index = index + 1
       print index;": ";
       for i = 1 to ls
           print c$(i);
       next
       print
   else
       lr = len(r$)
       for i = 1 to lr
           c$(ls - lr + 1) = mid$(r$, i, 1)
           r1$ = mid$(r$, 1, i - 1) + mid$(r$, i + 1)
           call orderperm r1$
       next
   end if
end sub



Append: Oh, my time for OP (Original Post) was ALLOT less than you report for N = 9! But can you use the OP code for word permutations just as fast?

[tsh73]

is 19861 vs 22109 "ALLOT less"?

It really heavily depends on computer.
On this one, first code works 2.75 times faster then your string code.
On some other it might even be other way round.

[B+]

My time for the original post was ALLOT less, like 1/3 of what you had reported. I thought the time doing it with strings was comparable but it wasn't but I didn't realize it until after I ran the code in original post.

But I can do permutations of strings.