Talk:Factorial base numbers indexing permutations of a collection: Difference between revisions
Talk:Factorial base numbers indexing permutations of a collection (view source)
Revision as of 18:34, 30 May 2019
, 4 years ago→Why not using the inverse of Knuth_shuffle
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
== Mojibake and misspellings ==
(As the task description is fairly difficult to read as it stands, I took a shot at revising it slightly, correcting misspellings and translating the erroneous Windows-1252->utf8 mojibake. Note that this is just my interpretation as I understood it. I am not the task author. Feel free to edit / correct anything I have gotten wrong.)
=============================================================================================================================
Line 17:
Observe that the least significant digit is base 2, the next; base 3, and so on. In general, an '''n'''-digit factorial base number will use the digits '''0..n''' in base '''n+1''' for each place '''1..n''' (from least to most significant.)
It is simple to produce a 1
0.0.0 -> 0123
Line 49:
starting with the '''most''' significant digit in the factorial base number.
* If '''g''' is greater than zero, rotate
* Increment '''m''' and repeat the first step using the next most significant digit until the factorial base number is exhausted.
For example: using the factorial base number '''2.0.1''' and '''Ω''' = '''0 1 2 3''' where place 0 in both is the most significant (left-most) digit/element.
* Step 1: '''m=0 g=2'''; Rotate places 0 through 2 left. '''Ω''' becomes 2 0 1 3▼
* Step 2: '''m=1 g=0'''; no action▼
* Step 3: '''m=2 g=1'''; Rotate places 3 through 3 left. '''Ω''' becomes 2 0 3 1▼
<br>
Line 78 ⟶ 77:
=============================================================================================================================
::Thanks--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 11:21, 10 December 2018 (UTC)
== Why not using the inverse of [http://rosettacode.org/wiki/Knuth_shuffle Knuth_shuffle] ==
this has the same factorial base number, but one has to do only length-1 swaps instead of rotation.
It ist easy to create a map between source and goal arrangement.
<pre>
source 1.3.2.0 with value,indices (0,3|1,0|2,1|3,1)
goal 0,1,2,3 with value,indices (0,0|1,1|2,2|3,3)
start index = 0
first swap 0 <-> 1 => index 0 <-> 3 -> update Value,Indices for swapped values ->
(Swap Index = 3 out of [0..3])
source 0.3.2.1 with value,indices (0,0|1,3|2,2|3,1)
index++ => 1
swap 3 <-> 1 => index 1 <-> 3
(Swap Index = 3 out of [index..3])
source 0.1.2.3 with value,indices (0,0|1,1|2,2|3,3)
index++ => 2
index 2 = index of value -> no swap;
source 0.1.2.3 with value,indices (0,0|1,1|2,2|3,3)
index++ => 3
index 3 = index of value -> no swap;
source 0.1.2.3 with value,indices (0,0|1,1|2,2|3,3)
</pre>
I see that the advantage of the rotation is the lexicographical order of generating the permutations, but what is it good for?
:see [[First perfect square in base N with N unique digits#Using Factorial base numbers indexing permutations of a collection]]--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 18:34, 30 May 2019 (UTC)
| |||