Как называется эта проблема генерации последовательности? Любые комментарии? - PullRequest
Новая
       15

Как называется эта проблема генерации последовательности? Любые комментарии?

2 голосов
/ 09 марта 2010

Мне нужно перебрать упорядоченную последовательность, которая определяется массивом чисел a i , i = 1. . n , где n - длина каждого элемента последовательности, а каждый a i определяет макс. количество возможных значений в позиции i в выходной последовательности.

* * 1 022 Пример: * 1 023 *

  • a = {10,10,10}
    Последовательность: 000, 001, 002, ... 999 (десятичные числа от 000 до 999)

  • a = (2,3,2}
    Последовательность: 000, 001, 010, 011, 020, 021, 100, 101, 110, 111, 120, 121

(Примечание: мне нужно не просто печатать последовательность, но мне нужно перебирать ее элементы, где каждый элемент - это массив, например, {1,2,1}.)

Прежде чем реализовать это, я хотел спросить, есть ли у кого-нибудь комментарии? Может быть, это известная проблема (имя?), И уже есть доступный код, или она сводится к другой известной проблеме? Оно имеет сходство с проблемой перестановок.

Ответы [ 3 ]

7 голосов
/ 09 марта 2010

Это декартово произведение .

В Python itertools.product создает такие списки кортежей. 

>>> import itertools
>>> list(itertools.product(*map(range, [2, 3, 2])))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 0), (0, 2, 1),
 (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (1, 2, 0), (1, 2, 1)]

На других языках легко создать декартово произведение, используя вложенные циклы: 

for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
        for (int k = 0; k < 2; k++)
            cout << i << j << k << endl;
1 голос
/ 10 марта 2010

Если вы используете C # (linq) и число факторов в декартовом произведении является статическим, то оно также может быть весьма элегантно выражено 

    static void Main(string[] args)
    {
        IEnumerable<int> firstFactor = Enumerable.Range(0, 2);
        IEnumerable<int> secondFactor = Enumerable.Range(0, 3);

        var cartesianProd =
             from first in firstFactor
             from second in secondFactor
             select new { First = first, Second = second };

        foreach (var tuple in cartesianProd)
        {
            Console.WriteLine("({0}, {1})", tuple.First, tuple.Second);
        }
        Console.ReadLine();
    }
1 голос
/ 09 марта 2010

Элементы последовательностей перечислены в лексографическом порядке.Также см. this (другая, но связанная проблема).

...