Unique Array Combinations

Question

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.

Additional rules:

• 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:
[]

Answer 1

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

Answer 2

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

Answer 3

Mathematica, 135 84 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!

Answer 4

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

Answer 5

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

Answer 6

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