Комбинации значений атрибутов

Question

Я борюсь с генерацией всех возможных комбинаций значений списка атрибутов.Например, для трех атрибутов A, B, C со следующими значениями: {a1, a2} для A, {b1, b2} для B и {c1, c2} для C, я должен получить 8 комбинаций:

a1,b1,c1
a1,b1,c2
a1,b2,c1
a1,b2,c2
a2,b1,c1
a2,b1,c2
a2,b2,c1
a2,b2,c2

Я использовал следующие две рекурсивные функции Java, где attribute_to_domain - это Map, где мы помещаем каждый атрибут как key, а его значения как value, и добавляем каждую комбинацию как<ArrayList<String> до enumerate_tuples как ArrayList<ArrayList<String>>

    public  void fillTuples(Map<String, Set<String>> attribute_to_domain, ArrayList<String> attributes, ArrayList<ArrayList<String>> enumerate_tuples)
{      
        for (Map.Entry<String, Set<String>> entrySet :attribute_to_domain.entrySet()) {
         String attribute=entrySet.getKey();
         attributes.add(attribute);
        }
    int pos = 0;
    Set<String> domain = attribute_to_domain.get(attributes.get(pos));
        for (Iterator<String> it = domain.iterator(); it.hasNext();) {
               String val = it.next();
            ArrayList<String> tuple=new ArrayList<String>();
            tuple.add(val);
                fillTuples(attribute_to_domain, attributes, 1, tuple, enumerate_tuples);
          tuple.remove(tuple.size()-1);
          assert(tuple.isEmpty());
          }

      }
public  void fillTuples(Map<String, Set<String>> attribute_to_domain, ArrayList<String> attributes, int pos, ArrayList<String> tuple,  ArrayList<ArrayList<String>>  enumerate_tuples)
{                              
    assert(tuple.size() == pos);
    if (pos == attributes.size())
    {      
       enumerate_tuples.add(tuple);
       return;
    }

        Set<String> domain = attribute_to_domain.get(attributes.get(pos));
        for (Iterator<String> it = domain.iterator(); it.hasNext();) {
          String val = it.next();
          tuple.add(val);
          fillTuples(attribute_to_domain, attributes, pos+1, tuple, enumerate_tuples);
          tuple.remove(tuple.size()-1);
        }

}

Проблема в том, что я получаю enumerate_tuples с пустыми элементами, и я не могу сохранить изменения, которые произошли с ним во время вызовов.

Как я могу решить эту проблему, пожалуйста?Заранее спасибо.

Answer 1

Пересмотрено с Декартово произведение произвольных множеств в Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class CartesianProduct {

    public static Set<Set<Object> > cartesianProduct(Set<?>... sets) {
        if (sets.length < 2)
            throw new IllegalArgumentException(
                    "Can't have a product of fewer than two sets (got " +
                    sets.length + ")");

        return _cartesianProduct(0, sets);
    }

    private static Set<Set<Object> > _cartesianProduct(int index, Set<?>... sets) {
        Set<Set<Object> > ret = new TreeSet<Set<Object> >(new Comparator<Set<Object> >() {
            @Override
            public int compare(Set<Object> o1, Set<Object> o2) {
                return o1.toString().compareTo(o2.toString());
            }
        });

        if (index == sets.length) {
            ret.add(new TreeSet<Object>());
        } else {
            for (Object obj : sets[index]) {
                for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                    set.add(obj);
                    ret.add(set);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Map<String, Set<String> > dataMap = new HashMap<String, Set<String> >();
        dataMap.put("A", new TreeSet<String>(Arrays.asList("a1", "a2")));
        dataMap.put("B", new TreeSet<String>(Arrays.asList("b1", "b2")));
        dataMap.put("C", new TreeSet<String>(Arrays.asList("c1", "c2")));

        System.out.println(cartesianProduct(dataMap.values().toArray(new Set<?>[0])));
    }

}

Answer 2

Существует более простое и быстрое решение, которое не требует рекурсии.

Количество выходных комбинаций может быть рассчитано дополнительно: умножение атрибутов в вашем случае 2*2*2, но оно верно для каждогосочетание.

Кроме того, мы можем рассчитать, какое значение будет помещено в каждую комбинацию на основе индекса комбинации.если мы предположим, что индекс комбинации изменяется от 0 до 7:
для A:
- комбинации 0-3 будут содержать a1
- комбинации 4-7 будут содержать a2
для B
- комбинации 0,1,4,5 будут содержать b1
- комбинации 2,3,6,7 будут содержать b2
для C
- комбинации 0,2,4,6 будет содержать c1
- комбинации 1,3,5,7 будут содержать c2

, поэтому формула для размещения значения основана на индексе комбинации, порядкеатрибуты (A сначала и т. д.) и порядок значений в атрибуте.

сложность этого алгоритма составляет o (n * m), где n - количество атрибутов и m - количество значений.