Geek asks and answers

Algorithm for returning all possible combinations of n objects taken from different bins

To make it more specific, I need an algorithm (recursive or not), which, given the integer n and the matrix as input, will return to me all the combinations that will have: 1) At least 1 object from each row 2) Will only have n objects

I feel that I can solve it easier if I just tried all the combinations and used those that have n objects and 1 from each row, but I believe that the algorithm can be much more efficient. I have also successfully coded an algorithm that will return all combinations of 1 object per line, but cannot expand it to a larger one. I encoded in Python, but any language is fine. Additional points to consider is that python passes objects per link. =)

Suppose the matrix is ​​a square. If someone wants to know why, this is part of a more complex graph algorithm that I am trying to solve.

Thanks everyone!

+3
source share
4 answers

, , . Python ( , ), , Python . , , , , ( , ).

:
PS1: - . n_edges - , . PS2: , .
PS3: , : (lol) , (lolindex).
PS4: , , , , . , .

def pickEdges(n_edges, newgraph):
    size = sum(len(v) for v in newgraph.itervalues())
    if (size == n_edges):
        print newgraph
        return

    for i in range(len(lol)):
        for j in range(len(lol[i])):
                tmpgraph = copy.deepcopy(newgraph)
                if (lol[i][j] not in tmpgraph[lolindex[i]]):
                       tmpgraph[lolindex[i]].append(lol[i][j])
                       pickEdges(n_edges, tmpgraph)
+1

, m - ; Racket:

(define (combinations m n)
  (cond
    ((and (zero? n) (null? m)) '(()))
    ((zero? n) '())
    ((null? m) '())
    ((null? (car m)) '())
    (else
      (append (combinations (cons (cdar m) (cdr m)) n)
              (map (lambda (ls) (cons (caar m) ls))
                   (append
                     (combinations (cons (cdar m) (cdr m)) (sub1 n))
                     (combinations (cdr m) (sub1 n))))))))
+2

, ? Javascript, :

function getWayStr(curr) {
  var nextAbove = -1;
  for (var i = curr + 1; i < waypoints.length; ++i) {
    if (nextAbove == -1) {
      nextAbove = i;
    } else {
      wayStr.push(waypoints[i]);
      wayStr.push(waypoints[curr]);
    }
  }
  if (nextAbove != -1) {
    wayStr.push(waypoints[nextAbove]);
    getWayStr(nextAbove);
    wayStr.push(waypoints[curr]);
  }
 }
0

! , "input bags" "", ( ) , , ( ).

:

set of valid combinations =
generate_combinations(list of input bags, number of objects in valid combination)

, , Python, generate_combinations , .

:

  • 1
  • n

:

  • ( )

№ 1 № 4 number of input bags <= n <= total number of objects in all bags

itertools Python , 2.6. Python, . .

>>> import itertools, collections
>>> input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
>>> output_bag_size = 5
>>> combos = generate_combinations(input_bags, output_bag_size)
>>> combos.next() #an arbitrary example
Bag([1,1,2,4,12])

, , itertools Python, . , , № 1. , .

>>> all_objects = itertools.chain.from_iterable(input_bags)
>>> all_objects
generator that returns [1, 2, 2, 3, 5, 1, 4, 5, 9, 12]
>>> combos = itertools.combinations(all_objects, output_bag_size)
>>> combos
generator that returns [(1,2,2,3,5), (1,2,2,3,1), (1,2,2,3,4), ...]

№ 1, ( ) 1 , . [1 ] [ ] , .

, [1 ] [ ] .

>>> combos_with_one_element_from_each_bag = itertools.product(*input_bags)
>>> for base_combo in combos_with_one_element_from_each_bag:
>>>     all_objects = list(itertools.chain.from_iterable(input_bags))
>>>     for seen in base_combo:
>>>         all_objects.remove(seen)
>>>     all_objects_minus_base_combo = all_objects
>>>     for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
>>>         yield itertools.chain(base_combo, remaining_combo)

, . _ , , base_combo.

>>> def remove_elements(iterable, elements_to_remove):
>>>     elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
>>>     for item in iterable:
>>>         if item not in elements_to_remove_copy:
>>>             yield item
>>>         else:
>>>             elements_to_remove_copy.remove(item)

An implementation of the Bag class might look like this:

>>> class Bag(collections.Counter):
>>>     def __iter__(self):
>>>         return self.elements()
>>>     def remove(self, item):
>>>         self[item] -= 1
>>>         if self[item] <= 0:
>>>             del self[item]

Full code

import itertools, collections

class Bag(collections.Counter):
    def __iter__(self):
        return self.elements()
    def remove(self, item):
        self[item] -= 1
        if self[item] <= 0:
            del self[item]
    def __repr__(self):
        return 'Bag(%s)' % sorted(self.elements())


def remove_elements(iterable, elements_to_remove):
    elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
    for item in iterable:
        if item not in elements_to_remove_copy:
            yield item
        else:
            elements_to_remove_copy.remove(item)

def generate_combinations(input_bags, output_bag_size):
    combos_with_one_element_from_each_bag = itertools.product(*input_bags)
    for base_combo in combos_with_one_element_from_each_bag:
        all_objects_minus_base_combo = remove_elements(itertools.chain.from_iterable(input_bags), base_combo)
        for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
            yield Bag(itertools.chain(base_combo, remaining_combo))

input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
output_bag_size = 5
combos = generate_combinations(input_bags, output_bag_size)
list(combos)

Complete this by adding an error checking code (e.g. output_bag_size> = len (input_bags).

Advantages of this approach: 1. Less support code (namely itertools) 2. No recursion. Python performance degrades with the height of the call stack, so minimizing recursion is beneficial. 3. Minimum memory consumption. This algorithm requires memory with constant space beyond what is consumed in the list of input bags.

0
source

More articles:


All Articles