Permutations with some identical elements: Difference between revisions
Permutations with some identical elements (view source)
Revision as of 11:38, 1 November 2022
, 1 year agoAdded Quackery.
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added Quackery.) |
||
Line 1,316:
[('A', 'A', 'B', 'B', 'B', 'C'), ('A', 'A', 'B', 'B', 'C', 'B'), ('A', 'A', 'B', 'C', 'B', 'B'), ('A', 'A', 'C', 'B', 'B', 'B'), ('A', 'B', 'A', 'B', 'B', 'C'), ('A', 'B', 'A', 'B', 'C', 'B'), ('A', 'B', 'A', 'C', 'B', 'B'), ('A', 'B', 'B', 'A', 'B', 'C'), ('A', 'B', 'B', 'A', 'C', 'B'), ('A', 'B', 'B', 'B', 'A', 'C'), ('A', 'B', 'B', 'B', 'C', 'A'), ('A', 'B', 'B', 'C', 'A', 'B'), ('A', 'B', 'B', 'C', 'B', 'A'), ('A', 'B', 'C', 'A', 'B', 'B'), ('A', 'B', 'C', 'B', 'A', 'B'), ('A', 'B', 'C', 'B', 'B', 'A'), ('A', 'C', 'A', 'B', 'B', 'B'), ('A', 'C', 'B', 'A', 'B', 'B'), ('A', 'C', 'B', 'B', 'A', 'B'), ('A', 'C', 'B', 'B', 'B', 'A'), ('B', 'A', 'A', 'B', 'B', 'C'), ('B', 'A', 'A', 'B', 'C', 'B'), ('B', 'A', 'A', 'C', 'B', 'B'), ('B', 'A', 'B', 'A', 'B', 'C'), ('B', 'A', 'B', 'A', 'C', 'B'), ('B', 'A', 'B', 'B', 'A', 'C'), ('B', 'A', 'B', 'B', 'C', 'A'), ('B', 'A', 'B', 'C', 'A', 'B'), ('B', 'A', 'B', 'C', 'B', 'A'), ('B', 'A', 'C', 'A', 'B', 'B'), ('B', 'A', 'C', 'B', 'A', 'B'), ('B', 'A', 'C', 'B', 'B', 'A'), ('B', 'B', 'A', 'A', 'B', 'C'), ('B', 'B', 'A', 'A', 'C', 'B'), ('B', 'B', 'A', 'B', 'A', 'C'), ('B', 'B', 'A', 'B', 'C', 'A'), ('B', 'B', 'A', 'C', 'A', 'B'), ('B', 'B', 'A', 'C', 'B', 'A'), ('B', 'B', 'B', 'A', 'A', 'C'), ('B', 'B', 'B', 'A', 'C', 'A'), ('B', 'B', 'B', 'C', 'A', 'A'), ('B', 'B', 'C', 'A', 'A', 'B'), ('B', 'B', 'C', 'A', 'B', 'A'), ('B', 'B', 'C', 'B', 'A', 'A'), ('B', 'C', 'A', 'A', 'B', 'B'), ('B', 'C', 'A', 'B', 'A', 'B'), ('B', 'C', 'A', 'B', 'B', 'A'), ('B', 'C', 'B', 'A', 'A', 'B'), ('B', 'C', 'B', 'A', 'B', 'A'), ('B', 'C', 'B', 'B', 'A', 'A'), ('C', 'A', 'A', 'B', 'B', 'B'), ('C', 'A', 'B', 'A', 'B', 'B'), ('C', 'A', 'B', 'B', 'A', 'B'), ('C', 'A', 'B', 'B', 'B', 'A'), ('C', 'B', 'A', 'A', 'B', 'B'), ('C', 'B', 'A', 'B', 'A', 'B'), ('C', 'B', 'A', 'B', 'B', 'A'), ('C', 'B', 'B', 'A', 'A', 'B'), ('C', 'B', 'B', 'A', 'B', 'A'), ('C', 'B', 'B', 'B', 'A', 'A')]
</pre>
=={{header|Quackery}}==
This is Narayana Pandita’s algorithm to generate the lexicographically next permutation from a given permutation, described in गणित कौमुदी ("Ganita Kaumudi", Google translation "Math skills", literal translation "Moonlight of Mathematics") pub. CE1356.
Starting with a list of characters (Initially in lexicographic order, <code>A < B < C < D < E < F etc.</code>, here we consider an arbitrary permutation in the middle of the sequence.)
<pre>[ B C F E D A ]</pre>
Scan from right to left to find the first character that is less than the previous character (N).
<pre>[ B C F E D A ]
↑</pre>
* If they are in reverse order <code>[ F E D C B A ]</code> that is the lexicographically last permutation.
Scan from right to left to find the first one that is greater than N.
<pre>[ B C F E D A ]
↑ ↑</pre>
Exchange them.
<pre>[ B C F E D A ]
↑ ↑</pre>
Reverse the order of the characters to the right of the first found character.
<pre>[ B C A D E F ]
↑</pre>
This is the next permutation.
* There is one permutation of the empty list, <code>[ ]</code>; it is the empty list, <code>[ ]</code>. The code presented here checks explicitly for this to avoid an array out of bounds error.
* When the lexicographically last permutation is detected, the code presented here reverses the whole list and skips the rest of the steps, returning the lexicographically first permutation, so repeated calls to <code>nextperm</code> will cycle through the permutations forever. This means there is no requirement to start with the lexicographically first permutation, but you will need to either precompute the number of permutations (<code>countperms</code>) or compare each permutation returned by <code>nextperm</code> to the first permutation.
<syntaxhighlight lang="Quackery"> [ dup [] = if done
0 over dup -1 peek
over size times
[ over i 1 - peek
tuck > if
[ rot drop i
unrot
conclude ] ]
2drop split
swap dup [] = iff
[ drop reverse ] done
-1 pluck
rot 0 unrot
dup size times
[ 2dup i peek
< if
[ rot drop i 1+
unrot
conclude ] ]
rot split
swap -1 pluck
dip
[ unrot join join
reverse ]
swap join join ] is nextperm ( [ --> [ )
[ 1 swap times
[ i^ 1+ * ] ] is ! ( n --> n )
[ 0 over
witheach +
!
swap witheach
[ ! / ] ] is permcount ( [ --> n )
[ [] swap
$ "" over
witheach
[ i^ char A +
swap of join ]
swap permcount
times
[ dup dip
[ nested join ]
nextperm ]
drop 70 wrap$ ] is task ( [ --> )
' [ 2 3 1 ] task</syntaxhighlight>
{{out}}
<pre>AABBBC AABBCB AABCBB AACBBB ABABBC ABABCB ABACBB ABBABC ABBACB ABBBAC
ABBBCA ABBCAB ABBCBA ABCABB ABCBAB ABCBBA ACABBB ACBABB ACBBAB ACBBBA
BAABBC BAABCB BAACBB BABABC BABACB BABBAC BABBCA BABCAB BABCBA BACABB
BACBAB BACBBA BBAABC BBAACB BBABAC BBABCA BBACAB BBACBA BBBAAC BBBACA
BBBCAA BBCAAB BBCABA BBCBAA BCAABB BCABAB BCABBA BCBAAB BCBABA BCBBAA
CAABBB CABABB CABBAB CABBBA CBAABB CBABAB CBABBA CBBAAB CBBABA CBBBAA
</pre>
'''Bonus code'''
Counting the permutations of "senselessness". It would be more efficient to use the formula given in the task description, n!/(a1! × a2! ... × ak!), (implemented as <code>countperms</code>), which yields 180180. This confirms that computation.
<syntaxhighlight lang="Quackery"> 0
$ "senselessness"
dup
[ rot 1+ unrot
nextperm
2dup = until ]
2drop
echo
say " permutations generated"</syntaxhighlight>
{{out}}
<pre>180180 permutations generated</pre>
=={{header|Raku}}==
| |||