CODEWITHSUNDEEP
arraysalgorithmpermutation
Devin
Devin

Reputation: 134

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.

Upvotes: 1

Views: 395

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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

Upvotes: 1

Related Questions