I asked a question on a couple of resources until I found the answer. I can not figure out how to optimally do the following algorithm:

Input data:

some positive integer N

some array of arrays (arrays are not repeated) containing arbitrary lists of numbers (from 1 to N), for example: {{1}, {1,2,7}, {3, 5}, ..., {1,2, 3,4,5,6}}

Output:

array of arrays of the following arrays: {{{1}, {2,3}, {4,7}, {5}, {6,8}, ...}, {{1,2}, {3, 9} , {4.7}, {5}, {6.8}, ...}, ...}

Any array of arrays from the output must contain all the numbers from the set (1, 2, ..., N) and not a single number should be repeated twice.

The returned array of arrays of arrays must contain all possible combinations of arrays of arrays that satisfy the conditions above.

Note, just in case, that the array of arrays, which is in the input data, may not contain any of the possible combinations (for example, {1, 2, 3}). Accordingly, this combination and should NOT be considered further.

Example:

Input data:

N = 4

Array of arrays:

 { {1}, {2}, {4}, {1,2}, {1,3}, {1,3,4}, {2,4}, {3,4} }

Returned data:

Array of arrays of arrays:

 { { {1},{2},{3,4} }, { {1,2},{3,4} }, { {1,3}, {2}, {4} }, { {1,3}, {2,4} }, { {1,3,4}, {2} } }

Update

My version:

At first, a table of the form is generated (let N = 5):

 11111 (все числа в одном массиве) 11112 (четыре первых числа в одном массиве и одно во втором) ... 12131 12133 ... 12345

Then from it, arrays of arrays are generated line by line (respectively):

 {1,2,3,4,5} {1,2,3,4},{5} ... {1,3,5},{2},{4} {1,3},{2},{4,5} ... {1},{2},{3},{4},{5}

Then go through the list and delete all variants containing at least one inaccessible array of numbers. Well, either you can immediately remove unnecessary options, but this is still not the way of the Jedi of some kind - all options are generated and unnecessary ones are deleted.

  • one
    Task C4 on the exam on computer science straight! Nifiga is not clear, but supposedly you can decide :) "I can not think of how to optimally do the following algorithm:" So you have already come up with an algorithm, it just works in one place? Introduce him, please. Maybe something clears up - fremail
  • Updated the question. - balalexv
  • one
    This is not for you here, but for the matcode. Just reformulate in the form: “Given a set of subsets of a finite set. Find (efficiently) all such subsets of this set that in each subset (1) the options are disjoint, and (2) their combination covers the original set. ”And so it smells like dynamic programming. - VladD
  • @VladD, this is really cool! - avp

1 answer 1

First option. It is necessary to go through all the combinations of L (length of the input array) for 1,2, ..., N. For sorting combinations it is reasonable to use the generation of combinations .

In other words. First, we take one array from the input data, check whether the elements will be from 1 to N. Next, we take the combinations of two arrays, combine (check that the elements are from 1 to N) and intersect (so that there are no repetitions) them. And so on. The maximum number of arrays participating in the combination can not be greater than N - the case when there are arrays on one element from 1 to N: {1}, {2}, ..., {N}.

The second option. For each array containing 1, we select arrays that complement, but do not intersect with, it. Those. we chose an array with a unit, then if there are no two in the array, we are looking for arrays with two. And so on, until we reach N. Accordingly, if there are non-intersecting arrays with numbers from 1 to N, we add this combination to the output.

For small N, arrays can be represented as a binary record of a number, and check for intersection / union by bit operations.