# Unique Array Combinations

The goal is to write a function or program which takes a set of integer arrays and returns a set of all possible arrays which meet the following criteria:

• A valid array must contain at least one number from each of the input arrays.
• A valid array cannot contain more than one number from a single input array.
• A valid array cannot contain duplicate values.

• Order of the output does not matter.
• Input/Output can be in any format you wish.
• If no valid arrays exist, the result should be an empty array or blank string.

Examples:

input:
[[1,2],
[2,1,0],
[0,3,1]]

output:
[[2,3],
[1]]
input:
[[1,3,4,7],
[1,2,5,6],
[3,4,8],
[8,9]]

output:
[[6,7,8],
[5,7,8],
[2,7,8],
[4,6,9],
[4,5,9],
[2,4,9],
[3,6,9],
[3,5,9],
[2,3,9],
[1,8]]
input:
[[1,2,3],
[2,3,4],
[1,4]]

output:
[]
• Related: Helping the farmer Jun 23, 2014 at 21:44
• Some explanation of what do you mean with 'overlap array'? Or a link... Jun 23, 2014 at 23:31
• @edc65 I've removed the term from the question to avoid confusion. They're just arrays. Jun 24, 2014 at 1:23
• @edc65, it's exact set cover with some of the input implicit. So the input sets are the elements to cover, and for each element of their union there is a set consisting of those input sets which contain that element. Jun 24, 2014 at 7:39

### GolfScript, 36 characters

:I[[]]\{{{|$}+1$/}%|}/{I{1$&,(},!*}, Input/output is standard GolfScript arrays, see in this example. :I # save input to variable I # part 1: generate all possible sets with zero or one numbers from each array # (zero or one is one char shorter than exactly one which would work also) [[]]\ # push the set with an empty set { # iterate over all input sets { # iterate over the numbers in the current set {|$}+1$/ # add this number to any set in the result }% | # join with the result set }/ # part 2: filter for valid sets (i.e. exactly one number from each array) { # start of filter block I{ # filter the input array of sets 1$&         #     calculate overlap of the current set with the input set
,(          #     remove if length is equal to one
},
!             #   is the list empty? (i.e. all input matched the filter criterion)
*             #   get rid of the second item on the stack
},              # end of filter block

# CJam, 35 bytes

q~:Q{m*{(+$_&}%}*_&{Q{1$&,(},,*!},p

Input is a list of list like:

[[1 3 4 7]
[1 2 5 6]
[3 4 8]
[8 9]]

and output is the list of unique lists that match all conditions, like for above input,

[[1 8] [2 3 9] [3 5 9] [3 6 9] [2 4 9] [4 5 9] [4 6 9] [2 7 8] [5 7 8] [6 7 8]]

How it works:

q~:Q                                 "Evaluate the input and store it in Q";
{          }*                    "Run this block for each adjacent pair in the array";
m*                              "Calculate Cartesian product of the pair";
{     }%                      "Map each cartesian product with the code block";
(+$"Flatten the array and sort it"; _& "Make the array unique"; _& "Only take unique cartesian products"; { }, "Filter the cartesian products based on the code block"; Q{ }, "Put Q on stack and run it through this filter"; 1$&            "Take ∩ of the input array with the cartesian product";
,(          "Check that length of the ∩ should be greater than 1";
,*!     "Now we have all the lists from the input list of list"
"which matched more than 1 element from this cartesian"
"product. So if this list is non empty, discard this"
"cartesian product";
p  "Print the filtered out valid unique arrays";

Try it online here

## Mathematica, 13584 72 bytes

f=Cases[Union/@Tuples@#,l_/;!MemberQ[#,k_/;Length@Intersection[k,l]>1]]&

Less golf:

f = Cases[
Union /@ Tuples@#,
l_ /; ! MemberQ[#, k_ /; Length@Intersection[k, l] > 1]
] &

This defines a function f that expects the input as a plain Mathematica list of lists, e.g.

f[{{1, 2}, {2, 1, 0}, {0, 3, 1}}]

Basically, I'm creating a list of all lists that fulfil conditions 1 and 3, and then I'm filtering out those that violate conditions 2. There might be a shortcut for one of the two, which I'll have to think about in more depth tomorrow. Found that shortcut!

# ruby, 143 114

Now shorter thanks to @Ventero.

h={};i=eval$*[0];v=i.flatten.uniq loop{h[a=v.sample(1+rand(v.size)).sort]||=h[a]||i.any?{|o|(o&a).size!=1}?1:p(a)} Usage: ruby uniq_arr.rb '[[1,3,4,7],[1,2,5,6],[3,4,8],[8,9]]' [2, 3, 9] [6, 7, 8] [3, 5, 9] [1, 8] [2, 7, 8] [4, 6, 9] [5, 7, 8] [2, 4, 9] [3, 6, 9] [4, 5, 9] Making it stop (eventually) is easy, but requires some code. It stops one h contains 2**l-1 elements, l being the number of unique elements in i, i.flatten.uniq.size http://ideone.com/zTlXZw • Some general improvements:$* is short for ARGV and allows dropping the whitespace after eval, loop{...} is a shorter infinite loop, rand is the same as Random.rand and p is a shorter way than $_ to get nil (the function does nothing and returns nil if called without arguments). Also, I think your reduce can be replaced with i.any?{|o|(o&a).size!=1}. Jun 24, 2014 at 8:14 ### Ruby — 80 73 characters @Howard knocks off 7 characters: f=->a{a[0].product(*a).map(&:uniq).uniq.select{|l|a.all?{|x|(l&x).one?}}} Some sample input: a = [[1, 2], [2, 1, 0], [0, 3, 1]] b = [[1,3,4,7], [1,2,5,6], [3,4,8], [8,9]] c = [[1,2,3], [2,3,4], [1,4]] d = [[]] e = [[1,2]] Output: f[a] # => [[1], [2, 3]] f[b] # => [[1, 8], [3, 2, 9], [3, 5, 9], [3, 6, 9], [4, 2, 9], [4, 5, 9], [4, 6, 9], [7, 2, 8], [7, 5, 8], [7, 6, 8]] f[c] # => [] f[d] # => [] f[e] # => [[1], [2]] ### Haskell — 90 characters I'm just learning Haskell, so I imagine this can be vastly improved. Same basic strategy as my Ruby solution. import Data.List f a=[l|l<-nub.map nub$sequence a,all(\x->length x==1)(map(intersect l)a)]
• I think you can also use the shorter version .product(*a) since the invalid solutions are filtered afterwards anyways. Jun 25, 2014 at 12:34

# Python, 157 characters

This is a straightforward brute-force implementation.

from itertools import*
a=input()
v=set(chain(*a))
print[x for x in chain(*[combinations(v,r)for r in range(len(v))])if all(1==len(set(x)&set(y))for y in a)]