[Алгоритм] Перебор разных символов в позициях. Не могу сообразить как.

0

0

Здравствуйте!

Есть одномерный массив. Нужно мне получить набор всех возможных варинтов массива. Возможные значения в каждой позиции известны. Например, исходные данные вот такие:

0 1 2 3 4
~+~+~+~+~
A A O S D
B C P   F
C X E   G
D   R   A
E       B
F       V 
G

Вверху диаграммы - позиции от 0 до 4, внизу в столбцах - возможные значения конкретной позиции.

Алгоритм должен работать с различной длиной одномерного массива. Количество возможных значений в каждом столбце, как видно, может быть разное.

Вопрос. Как должен выглядеть алгоритм полного перебора всех возможных состояний одномерного массива? Подойдет и рекурсивное решение, и итеративное. Я уже полдня думаю, никак не могу сообразить.

Ссылка

←	Препроцессинг с/c++

[git] локальные правки.

→

vector<string> S; 

void rec(string cur) { 
  if (cur.length() == S.size()) 
    cout << cur << endl; 
  else 
    for (size_t i = 0; i < S[cur.length()].length(); ++i) 
  rec(cur + S[cur.length()][i]); }

hired777 ★
(31.05.10 19:30:12 MSD)

Ответ на: комментарий от hired777 31.05.10 19:30:12 MSD

Что за быдлокод, вот красивое, эффективное и правильное решение:

#/usr/bin/python

import random

def foo(arr):
    n = 1
    count = 0
    for i in arr:
        n *= len(i)
    res = []
    while count < n:
        s = ''
        for i in arr:
            s += random.choice(i)
        if not s in res:
            count += 1
            res.append(s)
    return res


if __name__ == '__main__':
    res = foo(['ABCDEFG', 'ACX', 'OPER', 'S', 'DFGABV'])
    for i in res:
        print(i)

Rudcozt
(31.05.10 20:34:45 MSD)

Ответ на: комментарий от Rudcozt 31.05.10 20:34:45 MSD

Да-да...

Omploaded 'screenlog.0' to http://omploader.org/vNGdrcA

Omploaded '1.cpp' to http://omploader.org/vNGdrbg

Omploaded '1.py' to http://omploader.org/vNGdrbw

hired777 ★
(31.05.10 21:07:54 MSD)

> Как должен выглядеть алгоритм полного перебора всех возможных состояний одномерного массива?

При такой постановке задачи - в лоб. <captian> Количество вариантов для всего массива равно произведению всех вариантов для каждой позиции в массиве. </captain>

LamerOk ★★★★★
(31.05.10 22:24:10 MSD)