1

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.

Improve this question

1 Answer 1

Reset to default
1

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.)

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

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 which operation do you think would need repetition? I'm not following. The pseudocode I posted should return the full result you are after.
@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.)
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 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?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.