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

Комбинаторика, перебор всех сочетаний - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.61
~SERG
3 / 3 / 1
Регистрация: 06.08.2012
Сообщений: 26
20.01.2013, 15:52     Комбинаторика, перебор всех сочетаний #1
Предположим есть массив int ar[SIZE] = {0,0,0,0,0,1,1,1} (содержит 0 либо 1, число единиц(нулей) постоянно для всех
полученных сочетаний. Длина каждой полученной комбинации фиксирована и ровна SIZE = 8 .
Число полученных сочетаний = SIZE!/( n!*(SIZE - n)! ). Для данного случая 8!/(3!*(8-3)!) = 56
Может кто знает как получить все эти сочетания (без повторений).
Сам я решил эту задачу полным перебором (2^SIZE), с последующим выбором вариантов с требуемым числом 1.
Для больших SIZE - этот метод не подходит. Буду благодарен.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SeaMonster
 Аватар для SeaMonster
15 / 15 / 0
Регистрация: 31.12.2012
Сообщений: 101
20.01.2013, 16:36     Комбинаторика, перебор всех сочетаний #2
Мне сейчас лень писать код, но думаю можно попробовать так. Представим себе, что скажем 00000111 это число. Как из того же количества цифр получить следующее большее. Проверяем . Если в седьмой ячейке 0 и в восьмой 1, то меняем их местами и получаем новое сочетание. Если нет, то пробуем тоже для шестой и седьмой.
Т.е. что-то типа
C++
1
2
3
4
5
6
7
8
int ar[Size]//стартовым значением, сначала ноли потом в конце единички
 
for(;;){
 for(int i=Size-2;i>=0;i--){
  if(ar[i]==0 && ar[i+1]==1){ar[i]=1;ar[i+1]=0; направляем новый полученный куда надо и break; прерываем цикл}
  }
проверочка какая-то, не перешли ли все единички в самое начало, тогда значит все перебрали и это цикл тоже завершить
}
Добавлено через 15 минут
Этот алгоритм увы в топку... Попробовал так, понятно быстро написал, но он находит только часть комбинаций
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.01.2013, 18:42     Комбинаторика, перебор всех сочетаний #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <bitset>
 
int main()
{
    const int size = 8;
    int n = 3;
 
    for (int v = (1 << n) - 1; v < (1 << size); )
    {
        unsigned int t = (v | (v - 1)) + 1;
        v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
        std::cout << std::bitset<size> (v).to_string() << std::endl;;
    }
}
SeaMonster
 Аватар для SeaMonster
15 / 15 / 0
Регистрация: 31.12.2012
Сообщений: 101
20.01.2013, 18:52     Комбинаторика, перебор всех сочетаний #4
Вах код! Неясно как работает, но работает.

Правда так как именно у тебя он откомпилился, при запуске мигом все вывел и мигом закрылся...

Вот так с минимальными кривыми, но рабочими правками будет выводить по одному по нажатию клавиши
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    
 
#include <iostream>
#include <bitset>
#include<conio.h>
int main()
{
    const int size = 8;
    int n = 3;
 int schet=0;
    for (int v = (1 << n) - 1; v < (1 << size); )
    {
        unsigned int t = (v | (v - 1)) + 1;
        v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
        std::cout << std::bitset<size> (v).to_string() << std::endl;;
     std::cout<<"  schet"<<schet;getch();schet++;
    }
}
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
20.01.2013, 21:20     Комбинаторика, перебор всех сочетаний #5
Нормальный рабочий код, нужно добавить system("pause"); чтобы окно сразу же не закрывалось.
~SERG
3 / 3 / 1
Регистрация: 06.08.2012
Сообщений: 26
23.06.2013, 13:00  [ТС]     Комбинаторика, перебор всех сочетаний #6
Кто нибудь может пояснить суть алгоритма данных 2- строк:

unsigned int t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.06.2013, 13:07     Комбинаторика, перебор всех сочетаний
Еще ссылки по теме:

Организовать перебор всех возможных сочетаний C++
C++ Перебор всех значений трёх булевых переменных
C++ Быстрый перебор всех комбинаций 32 байтов

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.06.2013, 13:07     Комбинаторика, перебор всех сочетаний #7
Это все через коды грея считается.
Тут есть подробнее.
Yandex
Объявления
23.06.2013, 13:07     Комбинаторика, перебор всех сочетаний
Ответ Создать тему
Опции темы

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