Permutations: Difference between revisions
→{{header|Commodore BASIC}}: Add implementation
(→{{header|Commodore BASIC}}: Add implementation) |
|||
Line 2,640:
3,1,2
3,2,1</syntaxhighlight>
=={{header|Commodore BASIC}}==
Heap's algorithm, using a couple extra arrays as stacks to permit recursive calls.
<syntaxhighlight lang="Commodore BASIC">100 INPUT "HOW MANY";N
110 DIM A(N-1):REM ARRAY TO PERMUTE
120 DIM K(N-1):REM HOW MANY ITEMS TO PERMUTE (ARRAY AS STACK)
130 DIM I(N-1):REM CURRENT POSITION IN LOOP (ARRAY AS STACK)
140 S=0:REM STACK POINTER
150 FOR I=0 TO N-1
160 : A(I)=I+1: REM INITIALIZE ARRAY TO 1..N
170 NEXT I
180 K(S)=N:S=S+1:GOSUB 200:REM PERMUTE(N)
190 END
200 IF K(S-1)>1 THEN 270
210 REM PRINT OUT THIS PERMUTATION
220 FOR I=0 TO N-1
230 : PRINT A(I);
240 NEXT I
250 PRINT
260 RETURN
270 K(S)=K(S-1)-1:S=S+1:GOSUB 200:S=S-1:REM PERMUTE(K-1)
280 I(S-1)=0:REM LOOP CONTROL VARIABLE
290 IF I(S-1)>=K(S-1)-1 THEN 340:REM EXIT IF AT END
300 J=I(S-1):IF K(S-1) AND 1 THEN J=0:REM ELEMENT TO SWAP BASED ON PARITY OF K
310 T=A(J):A(J)=A(K(S-1)-1):A(K(S-1)-1)=T:REM SWAP
320 K(S)=K(S-1)-1:S=S+1:GOSUB 200:S=S-1:REM PERMUTE(K-1)
330 I(S-1)=I(S-1)+1:GOTO 290:REM LOOP
340 RETURN</syntaxhighlight>
{{Out}}
<pre>READY.
RUN
HOW MANY? 3
1 2 3
2 1 3
3 1 2
1 3 2
2 3 1
3 2 1
READY.</pre>
=={{header|Common Lisp}}==
| |||