CODEWITHSUNDEEP
pythonarraysalgorithm
WSBT
WSBT

Reputation: 36363

How to form an unique collection with one element taken from each array?

Say I have 3 integer arrays: {1,2,3}, {2,3}, {1}

I must take exactly one element from each array, to form a new array where all numbers are unique. In this example, the correct answers are: {2,3,1} and {3,2,1}. (Since I must take one element from the 3rd array, and I want all numbers to be unique, I must never take the number 1 from the first array.)

What I have done:

for a in array1:
    for b in array2:
        for c in array3:
            if a != b and a != c and b != c:
                AddAnswer(a,b,c)

This is brute force, which works, but it doesn't scale well. What if now we are dealing with 20 arrays instead of just 3. I don't think it's good to write a 20 nested for-loops. Is there a clever way to do this?

Upvotes: 1

Views: 73

Answers (3)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

You can think of this as finding a matching in a bipartite graph.

You are trying to select one element from each set, but are not allowed to select the same element twice, so you are trying to match sets to numbers.

You can use the matching function in the graph library NetworkX to do this efficiently.

Python example code:

import networkx as nx

A=[ [1,2,3],  [2,3],  [1] ]

numbers = set()
for s in A:
    for n in s:
        numbers.add(n)

B = nx.Graph()
for n in numbers:
    B.add_node('%d'%n,bipartite=1)
for i,s in enumerate(A):
    set_name = 's%d'%i
    B.add_node(set_name,bipartite=0)
    for n in s:
        B.add_edge(set_name,n)

matching = nx.maximal_matching(B)
if len(matching) != len(A):
    print 'No complete matching'
else:
    for number,set_name in matching:
        print 'choose',number,'from',set_name

This is a simple, efficient method for finding a single matching.

If you want to enumerate through all matchings you may wish to read: Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs by Takeaki UNO which gives O(V) complexity per matching.

Upvotes: 2

Francis Colas
Francis Colas

Reputation: 3647

A recursive solution (not tested):

def max_sets(list_of_sets, excluded=[]):
    if not list_of_sets:
        return [set()]
    else:
        res = []
        for x in list_of_sets[0]:
            if x not in excluded:
                for candidate in max_sets(list_of_sets[1:], exclude+[x]):
                    candidate.add(x)
                    res.append(candidate)
        return res

(You could probably dispense with the set but it's not clear if it was in the question or not...)

Upvotes: 0

jedwards
jedwards

Reputation: 30230

What about:

import itertools

arrs = [[1,2,3], [2,3], [1]]

for x in itertools.product(*arrs):
    if len(set(x)) < len(arrs): continue
    AddAnswer(x)

AddAnswer(x) is called twice, with the tuples:

(2, 3, 1)
(3, 2, 1)

Upvotes: 3

Related Questions