Algorithm Logic, Splitting Arrays
I'm not looking for a solution just pseudo code or logic that would help me derive an answer.
Given an array:
[1,2,3,4]
I want to split this into two arrays of varying lengths and contents whose sum lengths are equal to the length of the given array. It would be ideal without repetition.
Example output:
[[1],[2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4],[2, 3]]
[[1, 2, 3], [4]]
[[2], [1, 3, 4]]
[[2, 4], [1, 3]]
[[3], [1, 2, 4]]
More example:
[[1, 3, 4, 6, 8], [2, 5, 7]] //this is a possible combination of 1 through 8
//array
Intuitions:
First attempt involved pushing the starting number array[i] to the result array[0], the second loop moving the index for the third loop to start iterating as is grabbed sublists. Then fill the other list with remaining indices. Was poorly conceived...
Second idea is permutations. Write an algorithm that reorganizes the array into every possible combination. Then, perform the same split operation on those lists at different indexes keeping track of unique lists as strings in a dictionary.
[1,2,3,4,5,6,7,8]
^
split
[1,2,3,4,5,6,7,8]
^
split
[1,3,4,5,6,7,8,2]
^
split
I'm confident that this will produce the lists i'm looking for. However! i'm afraid it may be less efficient than I'd like due to the need for sorting when checking for duplicates and permutations is expensive in the first place.
Please respond with how you would approach this problem, and why.
arrays algorithm permutation
asked Nov 16 at 2:59
Devin
709
add a comment |
I'm not looking for a solution just pseudo code or logic that would help me derive an answer.
Given an array:
[1,2,3,4]
I want to split this into two arrays of varying lengths and contents whose sum lengths are equal to the length of the given array. It would be ideal without repetition.
Example output:
[[1],[2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4],[2, 3]]
[[1, 2, 3], [4]]
[[2], [1, 3, 4]]
[[2, 4], [1, 3]]
[[3], [1, 2, 4]]
More example:
[[1, 3, 4, 6, 8], [2, 5, 7]] //this is a possible combination of 1 through 8
//array
Intuitions:
First attempt involved pushing the starting number array[i] to the result array[0], the second loop moving the index for the third loop to start iterating as is grabbed sublists. Then fill the other list with remaining indices. Was poorly conceived...
Second idea is permutations. Write an algorithm that reorganizes the array into every possible combination. Then, perform the same split operation on those lists at different indexes keeping track of unique lists as strings in a dictionary.
[1,2,3,4,5,6,7,8]
^
split
[1,2,3,4,5,6,7,8]
^
split
[1,3,4,5,6,7,8,2]
^
split
I'm confident that this will produce the lists i'm looking for. However! i'm afraid it may be less efficient than I'd like due to the need for sorting when checking for duplicates and permutations is expensive in the first place.
Please respond with how you would approach this problem, and why.
arrays algorithm permutation
asked Nov 16 at 2:59
Devin
709
add a comment |
I'm not looking for a solution just pseudo code or logic that would help me derive an answer.
Given an array:
[1,2,3,4]
I want to split this into two arrays of varying lengths and contents whose sum lengths are equal to the length of the given array. It would be ideal without repetition.
Example output:
[[1],[2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4],[2, 3]]
[[1, 2, 3], [4]]
[[2], [1, 3, 4]]
[[2, 4], [1, 3]]
[[3], [1, 2, 4]]
More example:
[[1, 3, 4, 6, 8], [2, 5, 7]] //this is a possible combination of 1 through 8
//array
Intuitions:
First attempt involved pushing the starting number array[i] to the result array[0], the second loop moving the index for the third loop to start iterating as is grabbed sublists. Then fill the other list with remaining indices. Was poorly conceived...
Second idea is permutations. Write an algorithm that reorganizes the array into every possible combination. Then, perform the same split operation on those lists at different indexes keeping track of unique lists as strings in a dictionary.
[1,2,3,4,5,6,7,8]
^
split
[1,2,3,4,5,6,7,8]
^
split
[1,3,4,5,6,7,8,2]
^
split
I'm confident that this will produce the lists i'm looking for. However! i'm afraid it may be less efficient than I'd like due to the need for sorting when checking for duplicates and permutations is expensive in the first place.
Please respond with how you would approach this problem, and why.
arrays algorithm permutation
asked Nov 16 at 2:59
Devin
709
I'm not looking for a solution just pseudo code or logic that would help me derive an answer.
Given an array:
[1,2,3,4]
I want to split this into two arrays of varying lengths and contents whose sum lengths are equal to the length of the given array. It would be ideal without repetition.
Example output:
[[1],[2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4],[2, 3]]
[[1, 2, 3], [4]]
[[2], [1, 3, 4]]
[[2, 4], [1, 3]]
[[3], [1, 2, 4]]
More example:
[[1, 3, 4, 6, 8], [2, 5, 7]] //this is a possible combination of 1 through 8
//array
Intuitions:
First attempt involved pushing the starting number array[i] to the result array[0], the second loop moving the index for the third loop to start iterating as is grabbed sublists. Then fill the other list with remaining indices. Was poorly conceived...
Second idea is permutations. Write an algorithm that reorganizes the array into every possible combination. Then, perform the same split operation on those lists at different indexes keeping track of unique lists as strings in a dictionary.
[1,2,3,4,5,6,7,8]
^
split
[1,2,3,4,5,6,7,8]
^
split
[1,3,4,5,6,7,8,2]
^
split
I'm confident that this will produce the lists i'm looking for. However! i'm afraid it may be less efficient than I'd like due to the need for sorting when checking for duplicates and permutations is expensive in the first place.
Please respond with how you would approach this problem, and why.
arrays algorithm permutation
arrays algorithm permutation
asked Nov 16 at 2:59
Devin
709
asked Nov 16 at 2:59
Devin
709
edited Nov 16 at 3:08
asked Nov 16 at 2:59
Devin
709
asked Nov 16 at 2:59
Devin
709
asked Nov 16 at 2:59
Devin
709
709
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Pseudocode. The idea is to start with an item in one of the bags, and then to place the next item once in the same bag, once in the other.
function f(A):
// Recursive function to collect arrangements
function g(l, r, i):
// Base case: no more items
if i == length(A):
return [[l, r]]
// Place the item in the left bag
return g(l with A[i], r, i + 1)
// Also return a version where the item
// is placed in the right bag
concatenated with g(l, r with A[i], i + 1)
// Check that we have at least one item
if A is empty:
return
// Start the recursion with one item placed
return g([A[0]], , 1)
(PS see revisions for JavaScript code.)
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.[1, 2]- start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?
– גלעד ברקן
Nov 16 at 18:29
|
show 1 more comment
Your Answer
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: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53330795%2falgorithm-logic-splitting-arrays%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
Pseudocode. The idea is to start with an item in one of the bags, and then to place the next item once in the same bag, once in the other.
function f(A):
// Recursive function to collect arrangements
function g(l, r, i):
// Base case: no more items
if i == length(A):
return [[l, r]]
// Place the item in the left bag
return g(l with A[i], r, i + 1)
// Also return a version where the item
// is placed in the right bag
concatenated with g(l, r with A[i], i + 1)
// Check that we have at least one item
if A is empty:
return
// Start the recursion with one item placed
return g([A[0]], , 1)
(PS see revisions for JavaScript code.)
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.[1, 2]- start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?
– גלעד ברקן
Nov 16 at 18:29
|
show 1 more comment
Pseudocode. The idea is to start with an item in one of the bags, and then to place the next item once in the same bag, once in the other.
function f(A):
// Recursive function to collect arrangements
function g(l, r, i):
// Base case: no more items
if i == length(A):
return [[l, r]]
// Place the item in the left bag
return g(l with A[i], r, i + 1)
// Also return a version where the item
// is placed in the right bag
concatenated with g(l, r with A[i], i + 1)
// Check that we have at least one item
if A is empty:
return
// Start the recursion with one item placed
return g([A[0]], , 1)
(PS see revisions for JavaScript code.)
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.[1, 2]- start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?
– גלעד ברקן
Nov 16 at 18:29
|
show 1 more comment
Pseudocode. The idea is to start with an item in one of the bags, and then to place the next item once in the same bag, once in the other.
function f(A):
// Recursive function to collect arrangements
function g(l, r, i):
// Base case: no more items
if i == length(A):
return [[l, r]]
// Place the item in the left bag
return g(l with A[i], r, i + 1)
// Also return a version where the item
// is placed in the right bag
concatenated with g(l, r with A[i], i + 1)
// Check that we have at least one item
if A is empty:
return
// Start the recursion with one item placed
return g([A[0]], , 1)
(PS see revisions for JavaScript code.)
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
Pseudocode. The idea is to start with an item in one of the bags, and then to place the next item once in the same bag, once in the other.
function f(A):
// Recursive function to collect arrangements
function g(l, r, i):
// Base case: no more items
if i == length(A):
return [[l, r]]
// Place the item in the left bag
return g(l with A[i], r, i + 1)
// Also return a version where the item
// is placed in the right bag
concatenated with g(l, r with A[i], i + 1)
// Check that we have at least one item
if A is empty:
return
// Start the recursion with one item placed
return g([A[0]], , 1)
(PS see revisions for JavaScript code.)
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
edited Nov 16 at 17:04
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
answered Nov 16 at 3:30
גלעד ברקן
12.2k21439
12.2k21439
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.[1, 2]- start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?
– גלעד ברקן
Nov 16 at 18:29
|
show 1 more comment
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.[1, 2]- start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?
– גלעד ברקן
Nov 16 at 18:29
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
This operation would need to be done to all first indexes of A. A[0], A[1], A[2], correct? Also It looks like it produces repeating lists?
– Devin
Nov 16 at 16:58
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
– גלעד ברקן
Nov 16 at 17:00
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
@Devin also, please see JS code snippet in the answer's revisions -- it produces the partitions without duplicates. (I could restore it to the answer if you prefer.)
– גלעד ברקן
Nov 16 at 17:01
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
No that's fine, I haven't tested it. I was just looking at it. So how did you reason about splitting the arrays like this? Obviously each set was a split of 2 so left and right arrays, but why are you confident that this will produce every possible combination. Again i'm not looking for an answer as much as I am to change my thought process when approaching problems like this.
– Devin
Nov 16 at 17:23
@Devin well, let's see an example.
[1, 2] - start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?– גלעד ברקן
Nov 16 at 18:29
@Devin well, let's see an example.
[1, 2] - start with ([1], ). We take 2 and provide both L and R results -> ([1,2], ) and ([1], [2]). Now if we had three, each of those results from 2 would get a version with 3 in the left and 3 in the right: ([1,2], ) goes to ([1,2,3], ) ([1,2], [3]); and ([1], [2]) goes to ([1,3], [2]) ([1], [2,3]). So we'd get ([1,2,3], ) ([1,2], [3]) ([1,3], [2]) ([1], [2,3]) in total. Makes sense?– גלעד ברקן
Nov 16 at 18:29
|
show 1 more comment
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53330795%2falgorithm-logic-splitting-arrays%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
