How get the permutation of two lists but the elements of each list remain in the same order?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:
[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]
I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).
But I'm wondering if there may be a nicer way to do this?
edit: Some more elaborate info here
algorithms
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
$endgroup$
add a comment |
$begingroup$
So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:
[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]
I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).
But I'm wondering if there may be a nicer way to do this?
edit: Some more elaborate info here
algorithms
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
$endgroup$
$begingroup$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56
add a comment |
$begingroup$
So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:
[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]
I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).
But I'm wondering if there may be a nicer way to do this?
edit: Some more elaborate info here
algorithms
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
$endgroup$
So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:
[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]
I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).
But I'm wondering if there may be a nicer way to do this?
edit: Some more elaborate info here
algorithms
algorithms
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
edited Feb 19 at 15:25
Nimitz14
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
asked Feb 19 at 14:43
Nimitz14Nimitz14
1184
1184
$begingroup$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56
add a comment |
$begingroup$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56
$begingroup$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.
I hope this Python program speaks for itself:
from random import shuffle
def permutation(lst1, lst2, chi):
idx1 = 0
idx2 = 0
for i in range(len(lst1) + len(lst2)):
if chi[i] == '0':
yield lst1[idx1]
idx1 += 1
else:
yield lst2[idx2]
idx2 += 1
lst1 = 'xy'
lst2 = 'abc'
chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
Outputs:
11001
abxyc
10011
axybc
00111
xyabc
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
$endgroup$
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requiresdistinct_permutationsfrommore_itertools, just incase anyone else wonders how to do that
$endgroup$
– Nimitz14
Feb 19 at 15:30
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: "419"
;
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%2fcs.stackexchange.com%2fquestions%2f104554%2fhow-get-the-permutation-of-two-lists-but-the-elements-of-each-list-remain-in-the%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$
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.
I hope this Python program speaks for itself:
from random import shuffle
def permutation(lst1, lst2, chi):
idx1 = 0
idx2 = 0
for i in range(len(lst1) + len(lst2)):
if chi[i] == '0':
yield lst1[idx1]
idx1 += 1
else:
yield lst2[idx2]
idx2 += 1
lst1 = 'xy'
lst2 = 'abc'
chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
Outputs:
11001
abxyc
10011
axybc
00111
xyabc
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
$endgroup$
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requiresdistinct_permutationsfrommore_itertools, just incase anyone else wonders how to do that
$endgroup$
– Nimitz14
Feb 19 at 15:30
add a comment |
$begingroup$
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.
I hope this Python program speaks for itself:
from random import shuffle
def permutation(lst1, lst2, chi):
idx1 = 0
idx2 = 0
for i in range(len(lst1) + len(lst2)):
if chi[i] == '0':
yield lst1[idx1]
idx1 += 1
else:
yield lst2[idx2]
idx2 += 1
lst1 = 'xy'
lst2 = 'abc'
chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
Outputs:
11001
abxyc
10011
axybc
00111
xyabc
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
$endgroup$
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requiresdistinct_permutationsfrommore_itertools, just incase anyone else wonders how to do that
$endgroup$
– Nimitz14
Feb 19 at 15:30
add a comment |
$begingroup$
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.
I hope this Python program speaks for itself:
from random import shuffle
def permutation(lst1, lst2, chi):
idx1 = 0
idx2 = 0
for i in range(len(lst1) + len(lst2)):
if chi[i] == '0':
yield lst1[idx1]
idx1 += 1
else:
yield lst2[idx2]
idx2 += 1
lst1 = 'xy'
lst2 = 'abc'
chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
Outputs:
11001
abxyc
10011
axybc
00111
xyabc
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
$endgroup$
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.
I hope this Python program speaks for itself:
from random import shuffle
def permutation(lst1, lst2, chi):
idx1 = 0
idx2 = 0
for i in range(len(lst1) + len(lst2)):
if chi[i] == '0':
yield lst1[idx1]
idx1 += 1
else:
yield lst2[idx2]
idx2 += 1
lst1 = 'xy'
lst2 = 'abc'
chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
Outputs:
11001
abxyc
10011
axybc
00111
xyabc
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
edited Feb 19 at 14:57
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
answered Feb 19 at 14:48
Pål GDPål GD
7,0702342
7,0702342
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requiresdistinct_permutationsfrommore_itertools, just incase anyone else wonders how to do that
$endgroup$
– Nimitz14
Feb 19 at 15:30
add a comment |
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requiresdistinct_permutationsfrommore_itertools, just incase anyone else wonders how to do that
$endgroup$
– Nimitz14
Feb 19 at 15:30
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight!
$endgroup$
– Nimitz14
Feb 19 at 14:58
$begingroup$
Doing a full shuffle requires
distinct_permutations from more_itertools, just incase anyone else wonders how to do that$endgroup$
– Nimitz14
Feb 19 at 15:30
$begingroup$
Doing a full shuffle requires
distinct_permutations from more_itertools, just incase anyone else wonders how to do that$endgroup$
– Nimitz14
Feb 19 at 15:30
add a comment |
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f104554%2fhow-get-the-permutation-of-two-lists-but-the-elements-of-each-list-remain-in-the%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$
A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases.
$endgroup$
– Apass.Jack
Mar 6 at 10:47
$begingroup$
A partial Fisher–Yates shuffle might be better, too.
$endgroup$
– Apass.Jack
Mar 6 at 10:56