Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Составить уникальные комбинации из массива

Автор: azesmcar 25.5.2009, 17:30

Как-то непонятно тему назвал. Не сумел в короткий текст зажать мысль.
Ну да ладно, попробую тут обяснить.
Есть массив из 7 элементов
1 2 3 4 5 6 7
нужно получить все уникальные комбинации из 5 элементов, т.е.
1 2 3 4 5
1 2 3 4 6
1 2 3 4 7
1 2 3 5 6
...

писать рекурсию - не хочу, так как налицо явная возможность сделать итеративно, писать 5 вложенных циклов тоже как-то хреново.
может кто знает как правильнее это реализовать?

Спасибо.

Автор: Akina 25.5.2009, 18:20

Правильно - рекурсивно. ИМХО.

Добавлено через 2 минуты и 50 секунд

Цитата(azesmcar @ 25.5.2009, 18:30

)

писать 5 вложенных циклов

Достаточно двух - какая разница, выбирать оставляемые или выбрасываемые?

Автор: azesmcar 26.5.2009, 11:30

Цитата(Akina @ 25.5.2009, 18:20

)

Правильно - рекурсивно. ИМХО.

правильно избегать рекурсии там - где возможно без потерь качества кода решить итеративно. Тоже ИМХО разумеется smile

ну это как последний вариант.

Цитата(Akina @ 25.5.2009, 18:20

)

Достаточно двух - какая разница, выбирать оставляемые или выбрасываемые?

мысль понятна, но никак не додумаюсь как это реализовать

допустим есть у нас вот такой вот гадкий код, 5 вложенных циклов.
как это сделать двумя?

Код


void permutations(int* arr)
{
    for (int i1 = 0; i1 < 5; ++i1)
        for (int i2 = i1 + 1; i2 < 6; ++i2)
            for (int i3 = i2 + 1; i3 < 7; ++i3)
                for (int i4 = i3 + 1; i4 < 7; ++i4)
                    for (int i5 = i4 + 1; i5 < 7; ++i5)
                    {
                        std::cout << arr[i1] << arr[i2] << arr[i3] << arr[i4] << arr[i5] << std::endl;
                    }

}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    permutations(arr);
}

разумеется если выбирать между этим вариантом и рекурсией - я выберу рекурсию smile

просто хотелось бы итеративно.

Автор: Akina 26.5.2009, 11:39

Цитата(azesmcar @ 26.5.2009, 12:30

)

допустим есть у нас вот такой вот гадкий код, 5 вложенных циклов.
как это сделать двумя?

Ты выводишь элементы, индексы которых совпадают с управляющими переменными циклов. А надо просто сделать наоборот - выводить все элементы, кроме тех, индексы которых совпадают с управляющими переменными циклов.

Автор: Soah 26.5.2009, 11:50

http://algolist.ru/olimp/per_prb.php#z3

Цитата

Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}.

Пример: N=3, k=2,

подмножества {1,2}, {1,3}, {2,3}.

http://algolist.ru/olimp/per_sol.php#a3

Цитата

Воспользуемся следующим алгоритмом генерации сочетаний по k элементов из множества A:

В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число k). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,k.

Ищем B[j] с максимальным индексом j такое, что

B[j]<n+j-k,

увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[m], m>j, последний элемент B[k] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного k закончена.

Код


    const int n = 7;
    const int k = 5;
    int B[k];
    int j;

    for (j = 0; j < k; ++j)
        B[j] = j+1;

    showArray(B, k);
    for (j = k-1; j >=0 && B[0] <= n-k; --j)
        if (B[j] < n+j-k+1) {
            ++B[j];

            for (int m = j+1; m < k; ++m)
                B[m] = B[m-1] + 1;

            j = k;
            showArray(B, k);
        }

Автор: azesmcar 26.5.2009, 12:01

Soah

то что надо smile

+1

Добавлено через 48 секунд
плюсовать не разрешает, завтра сделаю smile