Can you sort a list like $(1, 2, 0, 3, 1, 5, 1)$ without arbitrary swaps?
$begingroup$
Background
Imagine you have a tuple of integers, say $t=(1, 2, 0, 3, 1, 5, 1)$. Then you can order the list with your favourite sorting algorithm and obtain $t'=(5, 3, 2, 1, 1, 1, 0)$. An alternative way of finding this element is
$$
t'=max{ gt : gin S_7 }
$$
for the symmetric group $S_7$, and where we mean max with respect to lexicographical order. Of course listing all possible permutations is inefficient, which is why we invented sorting.
Actual Question
Now take a subgroup $Gtrianglelefteq S_7$, which acts on tuples of integers; for our example take the group generated by the two cycles $(12)(34)$ and $(567)$. How do we find
$$
t''=max{ gt : gin G }
$$
without always calculating the entire orbit of $t$ under $G$?
What I Have
I suspect one can use a strong generating set for this; but I can't think of a way to do it.
An interesting reference I found is arXiv:1211.6261 where, in listing 1, the authors explain how to check whether a tuple is already the maximum within the orbit, with worst-case runtime being the size of the orbit. Since I'm looking for a sorting algorithm I would expect a worst-case runtime to be $Omega( n log n)$ for a tuple of length $n$; so generating the entire orbit is potentially exponentially worse.
Thanks!
- J
group-theory permutations algorithms sorting
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
$endgroup$
add a comment |
$begingroup$
Background
Imagine you have a tuple of integers, say $t=(1, 2, 0, 3, 1, 5, 1)$. Then you can order the list with your favourite sorting algorithm and obtain $t'=(5, 3, 2, 1, 1, 1, 0)$. An alternative way of finding this element is
$$
t'=max{ gt : gin S_7 }
$$
for the symmetric group $S_7$, and where we mean max with respect to lexicographical order. Of course listing all possible permutations is inefficient, which is why we invented sorting.
Actual Question
Now take a subgroup $Gtrianglelefteq S_7$, which acts on tuples of integers; for our example take the group generated by the two cycles $(12)(34)$ and $(567)$. How do we find
$$
t''=max{ gt : gin G }
$$
without always calculating the entire orbit of $t$ under $G$?
What I Have
I suspect one can use a strong generating set for this; but I can't think of a way to do it.
An interesting reference I found is arXiv:1211.6261 where, in listing 1, the authors explain how to check whether a tuple is already the maximum within the orbit, with worst-case runtime being the size of the orbit. Since I'm looking for a sorting algorithm I would expect a worst-case runtime to be $Omega( n log n)$ for a tuple of length $n$; so generating the entire orbit is potentially exponentially worse.
Thanks!
- J
group-theory permutations algorithms sorting
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
$endgroup$
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06
add a comment |
$begingroup$
Background
Imagine you have a tuple of integers, say $t=(1, 2, 0, 3, 1, 5, 1)$. Then you can order the list with your favourite sorting algorithm and obtain $t'=(5, 3, 2, 1, 1, 1, 0)$. An alternative way of finding this element is
$$
t'=max{ gt : gin S_7 }
$$
for the symmetric group $S_7$, and where we mean max with respect to lexicographical order. Of course listing all possible permutations is inefficient, which is why we invented sorting.
Actual Question
Now take a subgroup $Gtrianglelefteq S_7$, which acts on tuples of integers; for our example take the group generated by the two cycles $(12)(34)$ and $(567)$. How do we find
$$
t''=max{ gt : gin G }
$$
without always calculating the entire orbit of $t$ under $G$?
What I Have
I suspect one can use a strong generating set for this; but I can't think of a way to do it.
An interesting reference I found is arXiv:1211.6261 where, in listing 1, the authors explain how to check whether a tuple is already the maximum within the orbit, with worst-case runtime being the size of the orbit. Since I'm looking for a sorting algorithm I would expect a worst-case runtime to be $Omega( n log n)$ for a tuple of length $n$; so generating the entire orbit is potentially exponentially worse.
Thanks!
- J
group-theory permutations algorithms sorting
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
$endgroup$
Background
Imagine you have a tuple of integers, say $t=(1, 2, 0, 3, 1, 5, 1)$. Then you can order the list with your favourite sorting algorithm and obtain $t'=(5, 3, 2, 1, 1, 1, 0)$. An alternative way of finding this element is
$$
t'=max{ gt : gin S_7 }
$$
for the symmetric group $S_7$, and where we mean max with respect to lexicographical order. Of course listing all possible permutations is inefficient, which is why we invented sorting.
Actual Question
Now take a subgroup $Gtrianglelefteq S_7$, which acts on tuples of integers; for our example take the group generated by the two cycles $(12)(34)$ and $(567)$. How do we find
$$
t''=max{ gt : gin G }
$$
without always calculating the entire orbit of $t$ under $G$?
What I Have
I suspect one can use a strong generating set for this; but I can't think of a way to do it.
An interesting reference I found is arXiv:1211.6261 where, in listing 1, the authors explain how to check whether a tuple is already the maximum within the orbit, with worst-case runtime being the size of the orbit. Since I'm looking for a sorting algorithm I would expect a worst-case runtime to be $Omega( n log n)$ for a tuple of length $n$; so generating the entire orbit is potentially exponentially worse.
Thanks!
- J
group-theory permutations algorithms sorting
group-theory permutations algorithms sorting
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
edited Dec 19 '18 at 23:46
J Bausch
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
asked Dec 19 '18 at 22:21
J BauschJ Bausch
163
163
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06
add a comment |
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06
add a comment |
0
active
oldest
votes
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%2f3046935%2fcan-you-sort-a-list-like-1-2-0-3-1-5-1-without-arbitrary-swaps%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3046935%2fcan-you-sort-a-list-like-1-2-0-3-1-5-1-without-arbitrary-swaps%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
$begingroup$
I don't know much about this field - would an algorithm (assuming the entries are distinct) such as "maximize the first element; calculate the stabilizer of that entry then maximize the second element in that; etc." be reasonably efficient? It's certainly not hard to maximize the first element given a subgroup and this does solve the problem - I don't have a sense of how hard calculating the stabilizer is, though.
$endgroup$
– Milo Brandt
Dec 19 '18 at 23:53
$begingroup$
Neat idea! I assume a strong generating set would allow us to iteratively take the stabilizer for the first element, then the second, then the third... etc.. However, "it's certainly not hard to maximize the first element given a subgroup" - could you elaborate? I'm not sure I see how one would do that. Thanks!!
$endgroup$
– J Bausch
Dec 21 '18 at 9:42
$begingroup$
I found another reference; it appears this problem is $FP^{NP}$-complete. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.3058 But my general question remains: is there an algorithm that works well in practice? $EXP gg FP^{NP}$...
$endgroup$
– J Bausch
Dec 21 '18 at 10:06