Entry
Math: Combinatorics: Print: How to print all permutations, combinations, variations?
Apr 9th, 2007 11:34
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 09 April 2021 - 08:09 pm ----------------------
Math: Combinatorics: Print: How to print all permutations,
combinations, variations?
===
Permutations:
-----------------------------------------------------
-a general brute force approach:
-works for permutations, combinations, variations,...
-----------------------------------------------------
General Idea:
1) Use nested counters
2) Use some smaller then, equal to, unequal to, greater then,
relations between the counters
3) Use the start and end value of the counters
===
To give you the feeling:
start with 1 counter
FOR C = 1 TO 3
PRINT C
NEXT C
If you type RUN, this gives
1
2
3
===
What about 2 counters:
FOR counter1 = 1 TO 3
FOR counter2 = 1 TO 3
PRINT counter1, counter2
NEXT counter2
NEXT counter1
If you type RUN, this gives
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
---
What about 3 counters
FOR counter1 = 1 TO 3
FOR counter2 = 1 TO 3
FOR counter3 = 1 TO 3
PRINT counter1, counter2, counter3
NEXT counter3
NEXT counter2
NEXT counter1
Gives
1 1 1
1 1 2
1 1 3
etc...
3 3 1
3 3 2
3 3 3
---
You can of course expand this sequence to 4, 5, 6, 7, 8,..., whatever
you like amount of counters
---
Well, I hope you see that the permutations you are interested in, are
among the items in this list.
There are just too much, we have to find some way to restrict that
amount.
->For permutations, we ask that all the counters are UNEQUAL to each
other
******************************************
How to get the PERMUTATIONS?
Just use the 'unequal to' relation between the counters:
for example with 2 counters:
FOR counter1 = 1 TO 2
FOR counter2 = 1 TO 2
IF ( counter1 <> counter2 ) THEN PRINT counter1, counter2
NEXT counter2
NEXT counter1
If you type RUN, this gives:
1 2
2 1
So what you get here is the same as 2!
===
And how do you get 3!
You have to use 3 counters:
FOR counter1 = 1 TO 3
FOR counter2 = 1 TO 3
FOR counter3 = 1 TO 3
IF ( (counter1 <> counter2) AND
(counter1 <> counter3) AND
(counter2 <> counter3) )
THEN PRINT counter1, counter2, counter3
NEXT counter3
NEXT counter2
NEXT counter1
If you type RUN, this gives:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
===
And what about 4!
You use 4 counters
FOR counter1 = 1 TO 4
FOR counter2 = 1 TO 4
FOR counter3 = 1 TO 4
FOR counter4 = 1 TO 4
IF ( (counter1 <> counter2) AND
(counter1 <> counter3) AND
(counter1 <> counter4) AND
(counter2 <> counter3) AND
(counter2 <> counter4) AND
(counter3 <> counter4))
THEN PRINT counter1, counter2, counter3, counter4
NEXT counter4
NEXT counter3
NEXT counter2
NEXT counter1
If you type RUN, this gives
1 2 3 4
1 2 4 3
etc...
4 3 1 2
4 3 2 1
(totally 4! or thus 4x3x2x1=24 possibilities)
---
If you have 6 elements totally, you need 6 counters.
FOR counter1 = 1 TO 6
FOR counter2 = 1 TO 6
FOR counter3 = 1 TO 6
FOR counter4 = 1 TO 6
FOR counter5 = 1 TO 6
FOR counter6 = 1 TO 6
IF ((counter1 <> counter2) AND
(counter1 <> counter3) AND
(counter1 <> counter4) AND
(counter1 <> counter5) AND
(counter1 <> counter6) AND
(counter2 <> counter3) AND
(counter2 <> counter4) AND
(counter2 <> counter5) AND
(counter2 <> counter6) AND
(counter3 <> counter4) AND
(counter3 <> counter5) AND
(counter3 <> counter6) AND
(counter4 <> counter5) AND
(counter4 <> counter6) AND
(counter5 <> counter6))
THEN PRINT counter1, counter2, counter3, counter4, counter5,
counter6
NEXT counter6
NEXT counter5
NEXT counter4
NEXT counter3
NEXT counter2
NEXT counter1
===
Generalisation:
If you want to print N! possibilities
you need to nest N counters, running from 1 TO N
and these counters need to be unequal to each other
===
Note:
If you do not want to print the digits, but some characters,
put the characters (or words) in an array.
a$(1) = "A"
a$(2) = "B"
a$(3) = "C"
IF you say
PRINT counter1, counter2, counter3
you only get numbers 1 2 3
but
if you say
PRINT a$( counter1 ), a$( counter2 ), a$( counter3 )
you get the characters A, B, C
So to put it into practice:
FOR counter1 = 1 TO 3
FOR counter2 = 1 TO 3
FOR counter3 = 1 TO 3
PRINT a$( counter1 ), a$( counter2 ), a$( counter3 )
NEXT counter3
NEXT counter2
NEXT counter1
Gives
A A A
A A B
etc.
===
Of course you can also put words in the array:
a$( 1 ) = "John"
a$( 2 ) = "Doe"
a$( 3 ) = "USA"
and print them out.
John Doe USA
John USA Doe
Doe John USA
Doe USA John
USA John Doe
USA Doe John
===
Internet: see also:
---
BBCBASIC: Windows: Anagram: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/45013/fid/768
----------------------------------------------------------------------
