返回列表列表的叉积 [英] Return the cross product of a list of lists

问题描述

给出大小为n的列表，编写一个程序以返回每个列表中包含的元素的所有可能组合.

Given a list of size n, Write a program that returns all possible combination of elements contained in each list.

示例:

• 列表A ="x，z"
• 列表B ="a，b，c"
• 列表C ="o，p"

输出:

• x a o
• x a p
• x b o
• x b p
• .....
• z c p

顺序无关紧要，但是困难的部分是:您不能使用递归. 我的解决方案:

Order doesn't matter, but the hard part is: You can't use recursion. My solution:

void combos(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

如您所见，只有在我事先知道列表数量的情况下，它才有效.我很好奇是否递归是解决它的唯一方法.

As you can see, it only works if I know the number of lists before hand. I am curious if recursion is the only way to solve it.

推荐答案

请考虑一下如何增加数字，例如以3为基数的数字:

Think of it like how you increment a number, e.g. a base 3 number would go:

000
001
002
010
011
...
222

现在，将每个数字视为每个嵌套列表的索引.您将拥有与嵌套列表一样多的数字，即外部列表的大小.

Now think of each digit being the index into each of the nested lists. You will have as many digits as you have nested lists, i.e. the size of the outer list.

每个数字的基数"可能不同，并且是相应嵌套列表的大小.如果嵌套列表很大，则数字"可以是非常大的数字.

The "base" of each digit may differ, and is the size of the corresponding nested list. A "digit" can be a very large number if a nested list is large.

因此，您首先创建数字"或索引值的列表，然后将它们初始化为0.然后，您可以在这些索引处打印元素的值.然后，您递增最后一个索引值，并按需要进行滚动，就像正常数字一样，在第一个索引值滚动时停止.

So, you start by creating a list of "digit", or index values, initializing them to 0. You then print the values of the elements at those indices. You then increment the last index value, rolling over as needed, like you would a normal number, stopping when the first index value rolls over.

这是使用数组数组(即String[][])的Java实现.如果需要，您可以轻松地更改为List<List<String>>或List<String[]>.

Here is a Java implementation using arrays of arrays, i.e. String[][]. You can easily change to List<List<String>> or List<String[]> if needed.

@SafeVarargs
public static void printCombos(String[] ... lists) {
    if (lists.length == 0)
        throw new IllegalArgumentException("No lists given");
    for (String[] list : lists)
        if (list.length == 0)
            throw new IllegalArgumentException("List is empty");

    int[] idx = new int[lists.length];
    for (;;) {
        // Print combo
        for (int i = 0; i < lists.length; i++) {
            if (i != 0)
                System.out.print(' ');
            System.out.print(lists[i][idx[i]]);
        }
        System.out.println();

        // Advance to next combination
        for (int i = lists.length - 1; ++idx[i] == lists[i].length; ) {
            idx[i] = 0;
            if (--i < 0)
                return; // We're done
        }
    }
}

public static void main(String[] args) {
    String[][] data = { { "x", "z" }, { "a", "b", "c" }, { "o", "p" } };
    printCombos(data);
}

输出

x a o
x a p
x b o
x b p
x c o
x c p
z a o
z a p
z b o
z b p
z c o
z c p

如果使用列表而不是数组，则代码将使用get(int)，这可能并不总是对性能有好处，例如用于LinkedList.

If you use lists instead of arrays, then the code will use get(int), which may not always be good for performance, e.g. for LinkedList.

如果是这种情况，请将int[] idx替换为Iterator[]，并使用对应列表的迭代器初始化每个数组条目.然后，从相关列表中检索新的Iterator即可将数字"重置为0.

If that is the case, replace int[] idx with an Iterator[], initializing each array entry with an iterator for the corresponding list. Resetting a "digit" to 0 would then be done by retrieving a new Iterator from the list in question.

在这种情况下，它们甚至不必是列表，而可以是任何种类的集合，或更具体地说，可以是

In this case, they don't even have to be lists, but can be any kind of collection, or more specifically Iterable objects.

这篇关于返回列表列表的叉积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！