9erilous 9ermutations
Note: This is an attempt at recycling guest271314's permutation question(s)
There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, 123
has permutations:
123 132 213 231 312 321
When you find the differences between these, you get the sequence
9 81 18 81 9
Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.
Notably, if we use the next number up, 1234
, we get the sequence
9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9
Which extends the previous sequence while remaining palindromic around $693$. This pattern always holds, even when you start using more that 10
numbers, though the length of the sequence is $n!-1$ for $n$ numbers. Note that to use numbers above 0 to 9
, we don't change to a different base, we just multiply the number by $10^x$, e.g. $ [1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$.
Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:
1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1
Some other test cases (0 indexed):
23 => 657
119 => 5336
719 => 41015
5039 => 286694
40319 => 1632373
362879 => 3978052
100 => 1
1000 => 4
10000 => 3
100000 => 3
Rules:
- The submission can be any of:
- A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
- A program/function that takes a number $n$ and returns up to the $n$th index, either 0 or 1 indexed.
- A program/function that outputs/returns the sequence infinitely.
- The program should be capable of theoretically handling up to the $11!-1$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like $012345678910$ would be wrong.
- This is code-golf, so the shortest implementation for each language wins!
Notes:
- This is OEIS A217626
- I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
- The sequence works for any contiguous digits. For example, the differences between the permutations of $ [1,2,3,4]_{10} $ are the same as for $[-4,-3,-2,-1]_{10}$.
code-golf permutations
|
show 2 more comments
Note: This is an attempt at recycling guest271314's permutation question(s)
There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, 123
has permutations:
123 132 213 231 312 321
When you find the differences between these, you get the sequence
9 81 18 81 9
Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.
Notably, if we use the next number up, 1234
, we get the sequence
9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9
Which extends the previous sequence while remaining palindromic around $693$. This pattern always holds, even when you start using more that 10
numbers, though the length of the sequence is $n!-1$ for $n$ numbers. Note that to use numbers above 0 to 9
, we don't change to a different base, we just multiply the number by $10^x$, e.g. $ [1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$.
Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:
1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1
Some other test cases (0 indexed):
23 => 657
119 => 5336
719 => 41015
5039 => 286694
40319 => 1632373
362879 => 3978052
100 => 1
1000 => 4
10000 => 3
100000 => 3
Rules:
- The submission can be any of:
- A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
- A program/function that takes a number $n$ and returns up to the $n$th index, either 0 or 1 indexed.
- A program/function that outputs/returns the sequence infinitely.
- The program should be capable of theoretically handling up to the $11!-1$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like $012345678910$ would be wrong.
- This is code-golf, so the shortest implementation for each language wins!
Notes:
- This is OEIS A217626
- I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
- The sequence works for any contiguous digits. For example, the differences between the permutations of $ [1,2,3,4]_{10} $ are the same as for $[-4,-3,-2,-1]_{10}$.
code-golf permutations
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
1
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
1
Another interesting test case is $10!-1$ (3628799 => -83676269
) which I think is the first negative term.
– nwellnhof
Nov 11 at 14:18
1
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42
|
show 2 more comments
Note: This is an attempt at recycling guest271314's permutation question(s)
There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, 123
has permutations:
123 132 213 231 312 321
When you find the differences between these, you get the sequence
9 81 18 81 9
Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.
Notably, if we use the next number up, 1234
, we get the sequence
9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9
Which extends the previous sequence while remaining palindromic around $693$. This pattern always holds, even when you start using more that 10
numbers, though the length of the sequence is $n!-1$ for $n$ numbers. Note that to use numbers above 0 to 9
, we don't change to a different base, we just multiply the number by $10^x$, e.g. $ [1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$.
Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:
1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1
Some other test cases (0 indexed):
23 => 657
119 => 5336
719 => 41015
5039 => 286694
40319 => 1632373
362879 => 3978052
100 => 1
1000 => 4
10000 => 3
100000 => 3
Rules:
- The submission can be any of:
- A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
- A program/function that takes a number $n$ and returns up to the $n$th index, either 0 or 1 indexed.
- A program/function that outputs/returns the sequence infinitely.
- The program should be capable of theoretically handling up to the $11!-1$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like $012345678910$ would be wrong.
- This is code-golf, so the shortest implementation for each language wins!
Notes:
- This is OEIS A217626
- I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
- The sequence works for any contiguous digits. For example, the differences between the permutations of $ [1,2,3,4]_{10} $ are the same as for $[-4,-3,-2,-1]_{10}$.
code-golf permutations
Note: This is an attempt at recycling guest271314's permutation question(s)
There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, 123
has permutations:
123 132 213 231 312 321
When you find the differences between these, you get the sequence
9 81 18 81 9
Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.
Notably, if we use the next number up, 1234
, we get the sequence
9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9
Which extends the previous sequence while remaining palindromic around $693$. This pattern always holds, even when you start using more that 10
numbers, though the length of the sequence is $n!-1$ for $n$ numbers. Note that to use numbers above 0 to 9
, we don't change to a different base, we just multiply the number by $10^x$, e.g. $ [1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$.
Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:
1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1
Some other test cases (0 indexed):
23 => 657
119 => 5336
719 => 41015
5039 => 286694
40319 => 1632373
362879 => 3978052
100 => 1
1000 => 4
10000 => 3
100000 => 3
Rules:
- The submission can be any of:
- A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
- A program/function that takes a number $n$ and returns up to the $n$th index, either 0 or 1 indexed.
- A program/function that outputs/returns the sequence infinitely.
- The program should be capable of theoretically handling up to the $11!-1$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like $012345678910$ would be wrong.
- This is code-golf, so the shortest implementation for each language wins!
Notes:
- This is OEIS A217626
- I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
- The sequence works for any contiguous digits. For example, the differences between the permutations of $ [1,2,3,4]_{10} $ are the same as for $[-4,-3,-2,-1]_{10}$.
code-golf permutations
code-golf permutations
edited Nov 11 at 10:34
asked Nov 11 at 8:12
Jo King
20.7k247109
20.7k247109
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
1
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
1
Another interesting test case is $10!-1$ (3628799 => -83676269
) which I think is the first negative term.
– nwellnhof
Nov 11 at 14:18
1
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42
|
show 2 more comments
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
1
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
1
Another interesting test case is $10!-1$ (3628799 => -83676269
) which I think is the first negative term.
– nwellnhof
Nov 11 at 14:18
1
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
1
1
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
1
1
Another interesting test case is $10!-1$ (
3628799 => -83676269
) which I think is the first negative term.– nwellnhof
Nov 11 at 14:18
Another interesting test case is $10!-1$ (
3628799 => -83676269
) which I think is the first negative term.– nwellnhof
Nov 11 at 14:18
1
1
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42
|
show 2 more comments
5 Answers
5
active
oldest
votes
Jelly, 9 bytes
,‘œ?ŻḌI÷9
Try it online! (print the n'th element)
Try it online! (20 first elements)
Explanation:
I÷9 Compute the difference divided by 9 between
‘ the (n+1)th
œ? permutation
, and
the (n)th
œ? permutation
Ż of [0,1,2,...n]
Ḍ converted to decimal.
(Jelly has the builtin œ?
which computes the n
th permutation of a list in approximately linear time. Quite useful.)
add a comment |
Charcoal, 71 bytes
≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹
Try it online! Link is to verbose version of code. Explanation:
≔⟦N⊕θ⟧η
Get a list containing the input and one more than the input.
W⌈η
Repeat until both values are zero.
≧÷L⊞OυEη﹪κ⊕Lυη
Perform factorial base conversion on both values. This is the first time I've actually used ≧
on a list!
≔⁰δ
Clear the result.
F²«
Loop over each factorial base number.
≔Eυλζ
Make a list of the digits from 0 to length - 1.
≔⟦⟧η
Initialise the result to an empty list.
F⮌Eυ§κι«
Loop over the digits of the factorial base number.
⊞η§ζκ
Add the next permutation digit to the result.
≔Φζ⁻μκζ»
Remove that digit from the list.
≦⁻↨ηχδ»
Convert the permutation as a base 10 number and subtract the result so far from it.
I÷δ⁹
Divide the final result by 9 and cast to string.
add a comment |
Perl 6, 82 bytes
-2 bytes thanks to Jo King
->n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}
Try it online!
0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".
The following 80 byte version works for n up to 98!-2 and is a lot faster:
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}
Try it online!
The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}
Try it online!
add a comment |
JavaScript (Node.js), 134 bytes
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])
Try it online!
1-indexed.
@guest271314's opinion is right. Direct permutation computation is shorter...
Explanation
n=>( // Function -
F=_=> // Helper func to calculate length needed
f>n? // If f > n (meaning the length is enough) -
(
(
G=( // Helper func to calculate permutation value -
n,
z=0, // Initial values
x=f, // Made as copies because we need to alter
y=l, // these values and the function will be
b=[...a] // called twice
)=>
y? // If still elements remaining -
G(
n%(x/=y), // Get next element
+b.splice(n/x,1)+z*10, // And add to the temporary result
x,
y-1, // Reduce length
b // Remaining elements
)
:z // Otherwise return the permutation value
)(n--)-G(n) // Calculate G(n) - G(n - 1)
)/9 // ... the whole divided by 9
:F(
a.push(++l), // Otherwise l = l + 1, push l into the array
f*=l // ... and calculate l!
)
)(
a=[l=f=1] // Initial values
)
Original solution (159 bytes)
n=>(x=l=t=0n,P=(a,b=)=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n
Try it online!
Link is to a longer version made for performance. Array(n+1)
becomes Array(Math.min(n+1,15))
in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).
Explanation
I mean there's too much to explain.
n=>( // Function
x=l=t=0n, // Initialization
P=( // Function to determine the permutation -
a, // remaining items
b= // storage
)=>
n? // if we haven't reached the required permutation yet -
""+a? // if we haven't the last layer of loop -
a.map( // loop over the entries -
z=>
P( // recurse -
a.filter(y=>y-z), // pick out the selected number
[...b,z] // append to next
)
)
:( // if we are at the last layer -
v=b.reduce((u,y)=>u=u*10n+y), // calculate the value of the permutation
x? // if not the first number -
--n? // if not the last -
0 // do nothing
:t=v-x // else calculate difference
:0, // else do nothing
x=v // record ot anyway
)
:0 // else do nothing
)
(
[...Array(n+1)].map(_=>++l) // the list of numbers to permute
)&&t/9n // last difference divided by 9
FWIW, Given that this implementation does not return all differences up ton
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output(f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".
– guest271314
Nov 19 at 5:27
add a comment |
Pyth, 15 14 bytes
.+m/i.PdSQT9,h
Returns the nth term. Try it here.
.+ Find the differences between adjacent elements of
m mapping lambda d:
.PdSQ the dth permutation of input,
i T converted to base 10
/ 9 divided by 9
, over [Q+1,Q]
h Q
Q
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175693%2f9erilous-9ermutations%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
Jelly, 9 bytes
,‘œ?ŻḌI÷9
Try it online! (print the n'th element)
Try it online! (20 first elements)
Explanation:
I÷9 Compute the difference divided by 9 between
‘ the (n+1)th
œ? permutation
, and
the (n)th
œ? permutation
Ż of [0,1,2,...n]
Ḍ converted to decimal.
(Jelly has the builtin œ?
which computes the n
th permutation of a list in approximately linear time. Quite useful.)
add a comment |
Jelly, 9 bytes
,‘œ?ŻḌI÷9
Try it online! (print the n'th element)
Try it online! (20 first elements)
Explanation:
I÷9 Compute the difference divided by 9 between
‘ the (n+1)th
œ? permutation
, and
the (n)th
œ? permutation
Ż of [0,1,2,...n]
Ḍ converted to decimal.
(Jelly has the builtin œ?
which computes the n
th permutation of a list in approximately linear time. Quite useful.)
add a comment |
Jelly, 9 bytes
,‘œ?ŻḌI÷9
Try it online! (print the n'th element)
Try it online! (20 first elements)
Explanation:
I÷9 Compute the difference divided by 9 between
‘ the (n+1)th
œ? permutation
, and
the (n)th
œ? permutation
Ż of [0,1,2,...n]
Ḍ converted to decimal.
(Jelly has the builtin œ?
which computes the n
th permutation of a list in approximately linear time. Quite useful.)
Jelly, 9 bytes
,‘œ?ŻḌI÷9
Try it online! (print the n'th element)
Try it online! (20 first elements)
Explanation:
I÷9 Compute the difference divided by 9 between
‘ the (n+1)th
œ? permutation
, and
the (n)th
œ? permutation
Ż of [0,1,2,...n]
Ḍ converted to decimal.
(Jelly has the builtin œ?
which computes the n
th permutation of a list in approximately linear time. Quite useful.)
edited Nov 11 at 13:35
answered Nov 11 at 13:27
user202729
13.9k12551
13.9k12551
add a comment |
add a comment |
Charcoal, 71 bytes
≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹
Try it online! Link is to verbose version of code. Explanation:
≔⟦N⊕θ⟧η
Get a list containing the input and one more than the input.
W⌈η
Repeat until both values are zero.
≧÷L⊞OυEη﹪κ⊕Lυη
Perform factorial base conversion on both values. This is the first time I've actually used ≧
on a list!
≔⁰δ
Clear the result.
F²«
Loop over each factorial base number.
≔Eυλζ
Make a list of the digits from 0 to length - 1.
≔⟦⟧η
Initialise the result to an empty list.
F⮌Eυ§κι«
Loop over the digits of the factorial base number.
⊞η§ζκ
Add the next permutation digit to the result.
≔Φζ⁻μκζ»
Remove that digit from the list.
≦⁻↨ηχδ»
Convert the permutation as a base 10 number and subtract the result so far from it.
I÷δ⁹
Divide the final result by 9 and cast to string.
add a comment |
Charcoal, 71 bytes
≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹
Try it online! Link is to verbose version of code. Explanation:
≔⟦N⊕θ⟧η
Get a list containing the input and one more than the input.
W⌈η
Repeat until both values are zero.
≧÷L⊞OυEη﹪κ⊕Lυη
Perform factorial base conversion on both values. This is the first time I've actually used ≧
on a list!
≔⁰δ
Clear the result.
F²«
Loop over each factorial base number.
≔Eυλζ
Make a list of the digits from 0 to length - 1.
≔⟦⟧η
Initialise the result to an empty list.
F⮌Eυ§κι«
Loop over the digits of the factorial base number.
⊞η§ζκ
Add the next permutation digit to the result.
≔Φζ⁻μκζ»
Remove that digit from the list.
≦⁻↨ηχδ»
Convert the permutation as a base 10 number and subtract the result so far from it.
I÷δ⁹
Divide the final result by 9 and cast to string.
add a comment |
Charcoal, 71 bytes
≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹
Try it online! Link is to verbose version of code. Explanation:
≔⟦N⊕θ⟧η
Get a list containing the input and one more than the input.
W⌈η
Repeat until both values are zero.
≧÷L⊞OυEη﹪κ⊕Lυη
Perform factorial base conversion on both values. This is the first time I've actually used ≧
on a list!
≔⁰δ
Clear the result.
F²«
Loop over each factorial base number.
≔Eυλζ
Make a list of the digits from 0 to length - 1.
≔⟦⟧η
Initialise the result to an empty list.
F⮌Eυ§κι«
Loop over the digits of the factorial base number.
⊞η§ζκ
Add the next permutation digit to the result.
≔Φζ⁻μκζ»
Remove that digit from the list.
≦⁻↨ηχδ»
Convert the permutation as a base 10 number and subtract the result so far from it.
I÷δ⁹
Divide the final result by 9 and cast to string.
Charcoal, 71 bytes
≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹
Try it online! Link is to verbose version of code. Explanation:
≔⟦N⊕θ⟧η
Get a list containing the input and one more than the input.
W⌈η
Repeat until both values are zero.
≧÷L⊞OυEη﹪κ⊕Lυη
Perform factorial base conversion on both values. This is the first time I've actually used ≧
on a list!
≔⁰δ
Clear the result.
F²«
Loop over each factorial base number.
≔Eυλζ
Make a list of the digits from 0 to length - 1.
≔⟦⟧η
Initialise the result to an empty list.
F⮌Eυ§κι«
Loop over the digits of the factorial base number.
⊞η§ζκ
Add the next permutation digit to the result.
≔Φζ⁻μκζ»
Remove that digit from the list.
≦⁻↨ηχδ»
Convert the permutation as a base 10 number and subtract the result so far from it.
I÷δ⁹
Divide the final result by 9 and cast to string.
edited Nov 11 at 23:50
answered Nov 11 at 11:15
Neil
79.3k744177
79.3k744177
add a comment |
add a comment |
Perl 6, 82 bytes
-2 bytes thanks to Jo King
->n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}
Try it online!
0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".
The following 80 byte version works for n up to 98!-2 and is a lot faster:
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}
Try it online!
The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}
Try it online!
add a comment |
Perl 6, 82 bytes
-2 bytes thanks to Jo King
->n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}
Try it online!
0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".
The following 80 byte version works for n up to 98!-2 and is a lot faster:
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}
Try it online!
The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}
Try it online!
add a comment |
Perl 6, 82 bytes
-2 bytes thanks to Jo King
->n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}
Try it online!
0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".
The following 80 byte version works for n up to 98!-2 and is a lot faster:
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}
Try it online!
The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}
Try it online!
Perl 6, 82 bytes
-2 bytes thanks to Jo King
->n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}
Try it online!
0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".
The following 80 byte version works for n up to 98!-2 and is a lot faster:
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}
Try it online!
The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}
Try it online!
edited Nov 11 at 11:35
answered Nov 11 at 10:21
nwellnhof
6,48511125
6,48511125
add a comment |
add a comment |
JavaScript (Node.js), 134 bytes
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])
Try it online!
1-indexed.
@guest271314's opinion is right. Direct permutation computation is shorter...
Explanation
n=>( // Function -
F=_=> // Helper func to calculate length needed
f>n? // If f > n (meaning the length is enough) -
(
(
G=( // Helper func to calculate permutation value -
n,
z=0, // Initial values
x=f, // Made as copies because we need to alter
y=l, // these values and the function will be
b=[...a] // called twice
)=>
y? // If still elements remaining -
G(
n%(x/=y), // Get next element
+b.splice(n/x,1)+z*10, // And add to the temporary result
x,
y-1, // Reduce length
b // Remaining elements
)
:z // Otherwise return the permutation value
)(n--)-G(n) // Calculate G(n) - G(n - 1)
)/9 // ... the whole divided by 9
:F(
a.push(++l), // Otherwise l = l + 1, push l into the array
f*=l // ... and calculate l!
)
)(
a=[l=f=1] // Initial values
)
Original solution (159 bytes)
n=>(x=l=t=0n,P=(a,b=)=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n
Try it online!
Link is to a longer version made for performance. Array(n+1)
becomes Array(Math.min(n+1,15))
in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).
Explanation
I mean there's too much to explain.
n=>( // Function
x=l=t=0n, // Initialization
P=( // Function to determine the permutation -
a, // remaining items
b= // storage
)=>
n? // if we haven't reached the required permutation yet -
""+a? // if we haven't the last layer of loop -
a.map( // loop over the entries -
z=>
P( // recurse -
a.filter(y=>y-z), // pick out the selected number
[...b,z] // append to next
)
)
:( // if we are at the last layer -
v=b.reduce((u,y)=>u=u*10n+y), // calculate the value of the permutation
x? // if not the first number -
--n? // if not the last -
0 // do nothing
:t=v-x // else calculate difference
:0, // else do nothing
x=v // record ot anyway
)
:0 // else do nothing
)
(
[...Array(n+1)].map(_=>++l) // the list of numbers to permute
)&&t/9n // last difference divided by 9
FWIW, Given that this implementation does not return all differences up ton
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output(f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".
– guest271314
Nov 19 at 5:27
add a comment |
JavaScript (Node.js), 134 bytes
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])
Try it online!
1-indexed.
@guest271314's opinion is right. Direct permutation computation is shorter...
Explanation
n=>( // Function -
F=_=> // Helper func to calculate length needed
f>n? // If f > n (meaning the length is enough) -
(
(
G=( // Helper func to calculate permutation value -
n,
z=0, // Initial values
x=f, // Made as copies because we need to alter
y=l, // these values and the function will be
b=[...a] // called twice
)=>
y? // If still elements remaining -
G(
n%(x/=y), // Get next element
+b.splice(n/x,1)+z*10, // And add to the temporary result
x,
y-1, // Reduce length
b // Remaining elements
)
:z // Otherwise return the permutation value
)(n--)-G(n) // Calculate G(n) - G(n - 1)
)/9 // ... the whole divided by 9
:F(
a.push(++l), // Otherwise l = l + 1, push l into the array
f*=l // ... and calculate l!
)
)(
a=[l=f=1] // Initial values
)
Original solution (159 bytes)
n=>(x=l=t=0n,P=(a,b=)=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n
Try it online!
Link is to a longer version made for performance. Array(n+1)
becomes Array(Math.min(n+1,15))
in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).
Explanation
I mean there's too much to explain.
n=>( // Function
x=l=t=0n, // Initialization
P=( // Function to determine the permutation -
a, // remaining items
b= // storage
)=>
n? // if we haven't reached the required permutation yet -
""+a? // if we haven't the last layer of loop -
a.map( // loop over the entries -
z=>
P( // recurse -
a.filter(y=>y-z), // pick out the selected number
[...b,z] // append to next
)
)
:( // if we are at the last layer -
v=b.reduce((u,y)=>u=u*10n+y), // calculate the value of the permutation
x? // if not the first number -
--n? // if not the last -
0 // do nothing
:t=v-x // else calculate difference
:0, // else do nothing
x=v // record ot anyway
)
:0 // else do nothing
)
(
[...Array(n+1)].map(_=>++l) // the list of numbers to permute
)&&t/9n // last difference divided by 9
FWIW, Given that this implementation does not return all differences up ton
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output(f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".
– guest271314
Nov 19 at 5:27
add a comment |
JavaScript (Node.js), 134 bytes
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])
Try it online!
1-indexed.
@guest271314's opinion is right. Direct permutation computation is shorter...
Explanation
n=>( // Function -
F=_=> // Helper func to calculate length needed
f>n? // If f > n (meaning the length is enough) -
(
(
G=( // Helper func to calculate permutation value -
n,
z=0, // Initial values
x=f, // Made as copies because we need to alter
y=l, // these values and the function will be
b=[...a] // called twice
)=>
y? // If still elements remaining -
G(
n%(x/=y), // Get next element
+b.splice(n/x,1)+z*10, // And add to the temporary result
x,
y-1, // Reduce length
b // Remaining elements
)
:z // Otherwise return the permutation value
)(n--)-G(n) // Calculate G(n) - G(n - 1)
)/9 // ... the whole divided by 9
:F(
a.push(++l), // Otherwise l = l + 1, push l into the array
f*=l // ... and calculate l!
)
)(
a=[l=f=1] // Initial values
)
Original solution (159 bytes)
n=>(x=l=t=0n,P=(a,b=)=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n
Try it online!
Link is to a longer version made for performance. Array(n+1)
becomes Array(Math.min(n+1,15))
in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).
Explanation
I mean there's too much to explain.
n=>( // Function
x=l=t=0n, // Initialization
P=( // Function to determine the permutation -
a, // remaining items
b= // storage
)=>
n? // if we haven't reached the required permutation yet -
""+a? // if we haven't the last layer of loop -
a.map( // loop over the entries -
z=>
P( // recurse -
a.filter(y=>y-z), // pick out the selected number
[...b,z] // append to next
)
)
:( // if we are at the last layer -
v=b.reduce((u,y)=>u=u*10n+y), // calculate the value of the permutation
x? // if not the first number -
--n? // if not the last -
0 // do nothing
:t=v-x // else calculate difference
:0, // else do nothing
x=v // record ot anyway
)
:0 // else do nothing
)
(
[...Array(n+1)].map(_=>++l) // the list of numbers to permute
)&&t/9n // last difference divided by 9
JavaScript (Node.js), 134 bytes
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])
Try it online!
1-indexed.
@guest271314's opinion is right. Direct permutation computation is shorter...
Explanation
n=>( // Function -
F=_=> // Helper func to calculate length needed
f>n? // If f > n (meaning the length is enough) -
(
(
G=( // Helper func to calculate permutation value -
n,
z=0, // Initial values
x=f, // Made as copies because we need to alter
y=l, // these values and the function will be
b=[...a] // called twice
)=>
y? // If still elements remaining -
G(
n%(x/=y), // Get next element
+b.splice(n/x,1)+z*10, // And add to the temporary result
x,
y-1, // Reduce length
b // Remaining elements
)
:z // Otherwise return the permutation value
)(n--)-G(n) // Calculate G(n) - G(n - 1)
)/9 // ... the whole divided by 9
:F(
a.push(++l), // Otherwise l = l + 1, push l into the array
f*=l // ... and calculate l!
)
)(
a=[l=f=1] // Initial values
)
Original solution (159 bytes)
n=>(x=l=t=0n,P=(a,b=)=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n
Try it online!
Link is to a longer version made for performance. Array(n+1)
becomes Array(Math.min(n+1,15))
in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).
Explanation
I mean there's too much to explain.
n=>( // Function
x=l=t=0n, // Initialization
P=( // Function to determine the permutation -
a, // remaining items
b= // storage
)=>
n? // if we haven't reached the required permutation yet -
""+a? // if we haven't the last layer of loop -
a.map( // loop over the entries -
z=>
P( // recurse -
a.filter(y=>y-z), // pick out the selected number
[...b,z] // append to next
)
)
:( // if we are at the last layer -
v=b.reduce((u,y)=>u=u*10n+y), // calculate the value of the permutation
x? // if not the first number -
--n? // if not the last -
0 // do nothing
:t=v-x // else calculate difference
:0, // else do nothing
x=v // record ot anyway
)
:0 // else do nothing
)
(
[...Array(n+1)].map(_=>++l) // the list of numbers to permute
)&&t/9n // last difference divided by 9
edited Nov 19 at 7:53
answered Nov 12 at 3:19
Shieru Asakoto
2,380315
2,380315
FWIW, Given that this implementation does not return all differences up ton
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output(f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".
– guest271314
Nov 19 at 5:27
add a comment |
FWIW, Given that this implementation does not return all differences up ton
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output(f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".
– guest271314
Nov 19 at 5:27
FWIW, Given that this implementation does not return all differences up to
n
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output (f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".– guest271314
Nov 19 at 5:27
FWIW, Given that this implementation does not return all differences up to
n
, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output (f(n) - f(n-1))/9
for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.".– guest271314
Nov 19 at 5:27
add a comment |
Pyth, 15 14 bytes
.+m/i.PdSQT9,h
Returns the nth term. Try it here.
.+ Find the differences between adjacent elements of
m mapping lambda d:
.PdSQ the dth permutation of input,
i T converted to base 10
/ 9 divided by 9
, over [Q+1,Q]
h Q
Q
add a comment |
Pyth, 15 14 bytes
.+m/i.PdSQT9,h
Returns the nth term. Try it here.
.+ Find the differences between adjacent elements of
m mapping lambda d:
.PdSQ the dth permutation of input,
i T converted to base 10
/ 9 divided by 9
, over [Q+1,Q]
h Q
Q
add a comment |
Pyth, 15 14 bytes
.+m/i.PdSQT9,h
Returns the nth term. Try it here.
.+ Find the differences between adjacent elements of
m mapping lambda d:
.PdSQ the dth permutation of input,
i T converted to base 10
/ 9 divided by 9
, over [Q+1,Q]
h Q
Q
Pyth, 15 14 bytes
.+m/i.PdSQT9,h
Returns the nth term. Try it here.
.+ Find the differences between adjacent elements of
m mapping lambda d:
.PdSQ the dth permutation of input,
i T converted to base 10
/ 9 divided by 9
, over [Q+1,Q]
h Q
Q
edited Nov 19 at 23:25
answered Nov 19 at 8:15
lirtosiast
15.7k436107
15.7k436107
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175693%2f9erilous-9ermutations%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
What's the tie breaker for the bounty?
– nwellnhof
Nov 11 at 10:08
@nwellnhof Probably the first post
– Jo King
Nov 11 at 10:43
1
There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods?
– user202729
Nov 11 at 13:41
1
Another interesting test case is $10!-1$ (
3628799 => -83676269
) which I think is the first negative term.– nwellnhof
Nov 11 at 14:18
1
@user202729 I know, because basically we just need $O(Gamma^{-1}(n))$ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm
– Shieru Asakoto
Nov 13 at 4:42