Fastest way to find the i-th element of the n-th permutation of a sequence
$begingroup$
Let say I have a sequence [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and I want to retrieve the 4th element of the 1,000,000th permutation of this list.
I know how to compute the 1,000,000th permutation of the sequence using the algorithm explained here : Finding the n-th lexicographic permutation of a string
This permutation is [2 7 8 3 9 1 5 4 6 0], and so the 4th element is 3.
But is there a faster way to find "3", I mean except stopping computing the permutation after the 4th element?
permutations
asked Jan 1 at 13:48
fbparisfbparis
283
$endgroup$
add a comment |
$begingroup$
Let say I have a sequence [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and I want to retrieve the 4th element of the 1,000,000th permutation of this list.
I know how to compute the 1,000,000th permutation of the sequence using the algorithm explained here : Finding the n-th lexicographic permutation of a string
This permutation is [2 7 8 3 9 1 5 4 6 0], and so the 4th element is 3.
But is there a faster way to find "3", I mean except stopping computing the permutation after the 4th element?
permutations
asked Jan 1 at 13:48
fbparisfbparis
283
$endgroup$
add a comment |
$begingroup$
Let say I have a sequence [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and I want to retrieve the 4th element of the 1,000,000th permutation of this list.
I know how to compute the 1,000,000th permutation of the sequence using the algorithm explained here : Finding the n-th lexicographic permutation of a string
This permutation is [2 7 8 3 9 1 5 4 6 0], and so the 4th element is 3.
But is there a faster way to find "3", I mean except stopping computing the permutation after the 4th element?
permutations
asked Jan 1 at 13:48
fbparisfbparis
283
$endgroup$
Let say I have a sequence [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and I want to retrieve the 4th element of the 1,000,000th permutation of this list.
I know how to compute the 1,000,000th permutation of the sequence using the algorithm explained here : Finding the n-th lexicographic permutation of a string
This permutation is [2 7 8 3 9 1 5 4 6 0], and so the 4th element is 3.
But is there a faster way to find "3", I mean except stopping computing the permutation after the 4th element?
permutations
permutations
asked Jan 1 at 13:48
fbparisfbparis
283
asked Jan 1 at 13:48
fbparisfbparis
283
asked Jan 1 at 13:48
fbparisfbparis
283
asked Jan 1 at 13:48
fbparisfbparis
283
asked Jan 1 at 13:48
fbparisfbparis
283
283
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.
If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
$endgroup$
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
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.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3058492%2ffastest-way-to-find-the-i-th-element-of-the-n-th-permutation-of-a-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.
If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
$endgroup$
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
add a comment |
$begingroup$
I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.
If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
$endgroup$
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
add a comment |
$begingroup$
I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.
If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
$endgroup$
I have extensive experience with this and as far as I can tell there's no direct way to go to the $i$th element without computation. But look at it in perspective. The computation is not so bad. You can precompute factorials, then it's just a few operations to get an arbitrary index. Granted, the amount of operations increases with the index, but it's a very small number. It's negligible unless you're doing it a vast number of times.
If you are doing it a vast number of times, I'd say to avoid computing the element at all if that's possible with your application. If you need to do something like exchange adjacent elements or determine which is larger, that can be done in constant time without backing out the actual elements.
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
answered Jan 1 at 14:10
Matt SamuelMatt Samuel
39k63769
39k63769
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
add a comment |
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
Thanks a lot for your answer. Unfortunately I can't avoid computing this and I do it very frequently. Also I can't cache the permutations (256! is a huge number). If you're curious I'm using this for a home made cipher, source code here gist.github.com/fbparis/a5749da7efa88183976ff8ebb1174faf
$endgroup$
– fbparis
Jan 2 at 3:49
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
@fbparis One example where I never backed out a single element of the permutations is codereview.stackexchange.com/q/182610/155626 it probably won't help you much since it's so opaque. Also, for my application $n=16$ was the goal, which I never did end up achieving. $n=256$ will never, ever, be feasible for my problem, not if you turned the whole planet into a giant computer.
$endgroup$
– Matt Samuel
Jan 2 at 3:53
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
If you want to retrieve the full permutation, this algorithm is pretty fast and will work fine with n=256 or greater code.activestate.com/recipes/…
$endgroup$
– fbparis
Jan 2 at 4:09
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Oh, the part of my application that's infeasible for $n=256$ is the fact that the main loop has $256!$ iterations, as I'm summing over every permutation. Only a few operations per iteration, but I already estimated it would take $100$ days for $n=16$.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
$begingroup$
@fbparis Also have to store intermediate results.
$endgroup$
– Matt Samuel
Jan 2 at 4:12
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3058492%2ffastest-way-to-find-the-i-th-element-of-the-n-th-permutation-of-a-sequence%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
