Timeline for Most Efficient Way to List All $n$-bit Permutations
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2019 at 0:48 | history | edited | David C | CC BY-SA 4.0 |
added 164 characters in body
|
| Feb 22, 2017 at 17:53 | vote | accept | David C | ||
| Feb 22, 2017 at 13:35 | answer | added | Matt Timmermans | timeline score: 2 | |
| Feb 22, 2017 at 12:12 | comment | added | Yuval Filmus | Can you clarify your question? I'm not sure I understand it. What do you mean by "do such a listing using as few bits as possible"? Are you really just looking for an efficient way to record a permutation of all $n$-bit words? | |
| Feb 22, 2017 at 3:15 | comment | added | Yuval Filmus | It's a nice exercise. I haven't spelled out the details. | |
| Feb 22, 2017 at 3:12 | comment | added | Yuval Filmus | You can encode a permutation on $m$ values using a number in the range $0,\ldots,m!-1$ in many different ways. It's a nice exercise. You can think of this number from $0,\ldots,m!-1$ as encoding a number from $0,\ldots,m-1$, a number from $0,\ldots,m-2$, ..., and a number from $0,\ldots,0$. | |
| Feb 22, 2017 at 3:03 | comment | added | Yuval Filmus | If the order is predetermined and arbitrary, you need $\lceil \log_2 2^n! \rceil$ bits to describe it. | |
| Feb 22, 2017 at 2:59 | comment | added | David C | I'm not sure what you mean by a "higher level description"–but, for example, hexadecimal would not be allowed. | |
| Feb 22, 2017 at 2:56 | comment | added | Evil | Is the output format required to be list of bits or could it be a higher level description? The input is ordered list or only number of bits? Would LFSR with added 0 (here $n$ zeros) be a valid solution? | |
| Feb 22, 2017 at 2:23 | review | First posts | |||
| Feb 22, 2017 at 2:43 | |||||
| Feb 22, 2017 at 2:21 | history | asked | David C | CC BY-SA 3.0 |