Форум программистов, компьютерный форум CyberForum.ru

сгенерировать все варианты комбинации элементов - C++

Восстановить пароль Регистрация
 
Ника))
 Аватар для Ника))
39 / 39 / 8
Регистрация: 08.12.2010
Сообщений: 338
02.01.2016, 18:59     сгенерировать все варианты комбинации элементов #1
Вот ну не как не получается сделать следующее :
Надо из массива,к примеру, 4 элемента. Получиться все комбинации этих элементов. {0, 1} и {1, 0} одинаковые.
Вот дан массив: mas из 4 элементов должно поэтапно сгенерировать:
{0},{1},{2},{3},
{0,1},{0,2},{0,3},{0,1,2},{0,1,3},{0,1,2,3},
{1,2},{1,3},{1,2,3},
{2,3}
И мне не важно в каком порядке будут генерироваться эти варанты, главное что бы был весь перебор. Ни че путнего написать так не получилось...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GbaLog-
Не Эксперт C++
1477 / 622 / 176
Регистрация: 24.08.2014
Сообщений: 2,531
Записей в блоге: 1
Завершенные тесты: 2
02.01.2016, 19:15     сгенерировать все варианты комбинации элементов #2
Ника)), Вот так, нет?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>
#include <conio.h>
 
using namespace std;
 
void print( vector<int> vec ) {
    for( const auto& i : vec ) {
        cout << i << " ";
    }
    cout << endl;
}
 
int main() {
    vector<int> vec = { 0, 1, 2, 3 };
    while( next_permutation( vec.begin(), vec.end() ) ) print( vec );
    getch();
    return 0;
}
DocC
336 / 65 / 26
Регистрация: 22.12.2010
Сообщений: 138
02.01.2016, 19:28     сгенерировать все варианты комбинации элементов #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <locale>
 
using std::cout;
using std::cin;
using std::endl;
 
int main() {
    setlocale(LC_ALL,"Russian");
    int n;
    cout << "введите N для {0,1,...,N}:" << endl;
    cin >> n;
    cout << "перестановки без повторений" << endl;
    int *permutation = new int[n];
    for(int i = 0; i < n; i++ ) {
        for( int j = 0; j <= n; j++)
            permutation[j] = j;
        for(;;) {
            for(int k = 0; k <= i; k++)
                cout << permutation[k];
            cout << endl;
            if(permutation[0] + i != n ) {
                for(int l = i; l >= 0; l--) {
                    if(permutation[l] - l < n - i ) {
                        permutation[l]++;
                        if( l != i )
                            for(int c = l; c < i; c++ )
                                permutation[c+1] = permutation[c] + 1;
                        break;
                    }
                } 
            } else break;
        }
    }
    delete [] permutation;
    return 0;
}
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
02.01.2016, 19:37     сгенерировать все варианты комбинации элементов #4
Ника)), Булеан, что ли? (Все подмножества)
Но тогда у тебя пропущено пустое подмножества и { 0, 2, 3 }
Булеан имеет 2n элементов. Для n = 4 24 = 16, а у тебя только 14.
Алгоритм довольно прост. Генерируются все двоичные последовательности длины n (0000 ... 1111) 1 на k-м месте означает, что k-й элемент включен в подмножество.
Для генерации достаточно провернуть цикл от 0 до 2n и разобрать числа по битикам.

Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
int p = (1<<N);
for(i=0; i<p; i++) {
 cout << i << ": {";
 for (int j=0; j < N; j++) {
   if ((i>>j)&1) cout << j << " ";
 }
 cout << " }" << endl;
}
DocC
336 / 65 / 26
Регистрация: 22.12.2010
Сообщений: 138
02.01.2016, 19:41     сгенерировать все варианты комбинации элементов #5
К своему посту могу добавить, что нужно ещё вывести {0,1,2,3} (итого получится 15 комбинаций)
Но думаю это Вам уже не составит труда.

Проверить можно, посчитав количество подобных комбинаций, по формуле http://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{n} - 1 (здравствуйте, ханойская башня).
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
02.01.2016, 19:58     сгенерировать все варианты комбинации элементов #6
Цитата Сообщение от DocC Посмотреть сообщение
Проверить можно, посчитав количество подобных комбинаций,
Можно. Только вот зачем чесать левой задней лапой правое ухо, если можно все сделать буквально в лоб. Ибо каждое число (его двоичное представление) непосредственно дают одну из комбинаций?
ЗЫ. Если пустое множество включать не нужно, в строке 2 кода из поста 4
C++
1
for(int i=1; ...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2016, 20:13     сгенерировать все варианты комбинации элементов
Еще ссылки по теме:

C++ Все возможные комбинации длины k из 0 и 1
C++ Найти все возможные комбинации по номеру карты
Все возможные комбинации из 10 цифр по n C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ника))
 Аватар для Ника))
39 / 39 / 8
Регистрация: 08.12.2010
Сообщений: 338
02.01.2016, 20:13  [ТС]     сгенерировать все варианты комбинации элементов #7
Все это дело мне надо сделать на векторах, у меня есть 4 вектора, там хранятся структуры ( но это не важно, так как работа с индексами) :
C++
1
2
3
4
    vector<TeamAuto*> Zad_Low_Sl;  
    vector<TeamAuto*> Zad_Norm_Sl;
    vector<TeamAuto*> Zad_Hard_Sl;
    vector<TeamAuto*> Zad_Ost_Sl;
В них забиваются задания с БД. И вот мне надо перебрать все доступные комбинации этих заданий...
Могут быть несколько из первого, второго, третьего, четвертого... Поэтому я и попросил помочь только с одним =)

Добавлено через 9 минут
Что то я тут подумал, что если заданий будет 20 то вариантов будет очень много.
Может посоветуете в таком случае правильный подход.
Мне необходимо генерировать варианты теста из существующих заданий в БД. Задания разделены по сложности(векторы).
С указанной сложностью и затрачиваемым временем. Какое оптимальное решение есть для таких задач?
Yandex
Объявления
02.01.2016, 20:13     сгенерировать все варианты комбинации элементов
Ответ Создать тему
Опции темы

Текущее время: 03:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru