0

假设我们要给出一些项目的列表列表，比如字符串。

list 1: "a", "b", "c"

list 2: "d", "e", "f"

list 3: "1", "2", "3"


results: (a, d, 1), (a, d, 2), ... (c, f, 3)

（真正的用例与字符串等无关，这只是一个模型）

我写了一个递归方法来做到这一点，但我对它不满意，因为它创建了很多被扔掉的临时集（是的，我知道在 java 中创建对象很便宜，通常 cpu 指令比 C 中的 malloc 少（源: Java Concurrency in Action, p241)，eden GC 很便宜，等等等等。幽默我 :)。

void combine(List<List<String>> itemLists, List<Set<String>> combinations, Set<String> partial) {
    if (itemLists == null || itemLists.isEmpty()) return;
    List<String> items = itemLists.get(0);
    for (String s : items) {
        Set<String> tmpSet = new HashSet<>(partial);
        tmpSet.add(s);
        if (itemLists.size() == 0) //termination test
            combinations.add(tmpSet);
        else
            combine(itemLists.subList(1, itemLists.size()), combinations, tmpSet);
    }
}

那么，你会怎么做呢？

编辑：要清楚，我不想创建排列。我想创建 sizeof(list of lists) 大的集合。

4

3 回答 3

3

您正在寻找的是“笛卡尔积”。

如果您可以使用 Sets 而不是 Lists，您可以使用Sets.cartesianProduct. 当您遍历生成的列表时，仍然分配了一些垃圾......但几乎没有其他方法那么多。

（请注意，作为一种常见的库方法，它已经过非常详尽的测试，因此与从 SO 中粘贴数十行代码相比，您可以对它更有信心。）

仅供参考，也有人提出要求，Lists.cartesianProduct但我认为没有人在努力。

于 2012-05-10T14:45:16.357 回答
1

您想要一个所有可能集合的列表，其中包含每个提供的列表中的一个值，假设列表的数量是可变的并且这些列表的大小也是可变的。正确的？

那么这样的事情呢？

static List<Set<String>> combine(List<List<String>> itemLists)
{
    // Calculate how many combinations we'll need to build
    int remainingCombinations = itemLists.get(0).size();
    for(int i=1; i<itemLists.size(); i++)
    {
        remainingCombinations *= itemLists.get(i).size();
    }

    List<Set<String>> allSets = new ArrayList<Set<String>>();

    // Generate this combination
    for (;remainingCombinations > 0; remainingCombinations --)
    {
        Set<String> currentSet = new HashSet<String>();
        int positionInRow = remainingCombinations;

        // Pick the required element from each list, and add it to the set.
        for(int i=0; i<itemLists.size(); i++)
        {
            int sizeOfRow = itemLists.get(i).size();
            currentSet.add(itemLists.get(i).get(positionInRow % sizeOfRow));
            positionInRow /= sizeOfRow;
        }

        allSets.add(currentSet);
    }
    return allSets;
}
于 2012-05-09T01:14:48.057 回答
1

这更有效：以与计数相同的方式处理它（每个“位置”都是您的列表之一，并且可以进入该位置的每个“数字”都是您列表的一个元素）：

List<Set<String>> combine( List<List<String>> input ){

    final int n = input.size();
    int[] index = new int[n];

    List<Set<Sting>> result = new List<>();

    int position = 0;
    while( position < n ){ // "overflow" check

        // Add set to result.
        Set<String> set = new HashSet<>();
        for( int i=0; i<n; i++ )
            set.add( input.get(i).get( index[i] ) );
        result.add( set );

        // Now the "hard" part: increment the index array
        position = 0;
        while( position < n ){

            if( index[ position ] < input.get( position ).size() ){
                index[position]++;
                break;
            }
            else // carry
                index[ position++ ] = 0;
        }
    }
    return result;
}

（未经测试，可能有一些错误，但主要思想就在那里）。一般来说，递归比迭代慢。

于 2012-05-09T01:14:58.563 回答