Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.61
~SERG
3 / 3 / 1
Регистрация: 06.08.2012
Сообщений: 26
#1

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

20.01.2013, 15:52. Просмотров 6068. Ответов 6
Метки нет (Все метки)

Предположим есть массив 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 - этот метод не подходит. Буду благодарен.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2013, 15:52
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Комбинаторика, перебор всех сочетаний (C++):

Перебор и вывод всех возможных сочетаний - C++
Итак,здравствуйте форумчане. Привела меня к вам интересная задачка. Вводится слово,заранее не известно количество букв необходимо...

Организовать перебор всех возможных сочетаний - C++
Затрудняюсь с алгоритмом. Как можно организовать перебор всех возможных группировок? Имеется несколько романов одного писателя. Для...

Перебор всех возможных сочетаний заданных переменных - C++
Чтобы не создавать новую тему, напишу здесь. Есть несколько переменных - около 20, часть переменных может иметь 2 значения, часть - три...

Комбинаторика, вычислить число сочетаний C(N, K) - C++
When I was in army, sometimes (about once a week) our unit was faced a charming alternative: most of the hands are to be sent to...

Перебор неповторяющихся сочетаний - C++
Здравствуйте. Существует ли какая-нибудь функция на c++, которая перебирает все возможные перестановки без повторений элементов? например...

Реализовать перебор всех возможных IP-адресов (С++) - C++
Реализовать перебор всех возможных IP-адресов, начиная с 0.0.0.0, заканчивая 255.255.255.0. (проще говоря перебор всех возможных комбинаций...

6
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 минут
Этот алгоритм увы в топку... Попробовал так, понятно быстро написал, но он находит только часть комбинаций
0
diagon
Higher
1936 / 1202 / 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;;
    }
}
2
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++;
    }
}
0
isaak
107 / 44 / 9
Регистрация: 17.10.2010
Сообщений: 685
20.01.2013, 21:20 #5
Нормальный рабочий код, нужно добавить system("pause"); чтобы окно сразу же не закрывалось.
0
~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);
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.06.2013, 13:07 #7
Это все через коды грея считается.
Тут есть подробнее.
1
23.06.2013, 13:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.06.2013, 13:07
Привет! Вот еще темы с ответами:

Быстрый перебор всех комбинаций 32 байтов - C++
Здравствуйте, как можно очень быстро перебрать все комбинации 32 байтов, с записью результата в string для сравнения строк ? то-есть...

Перебор всех значений трёх булевых переменных - C++
Вобщем мне надо проверить функцию на тавтологию, для этого как я понимаю надо проверить чтобы конечная функция была всегда истинной при...

Перебор всех слов латинского алфавита длиной 1-4 букв - C++
Задали такую программу, а как ее писать - даже не знаю) Конечно представляю, что 1 пункт массив, а вот дальше... &quot;1)Перебор всех...

Перебор всех возможных подмножеств множества целых чисел - C++
Всем привет)))) Пожалуйста, помогите решить задачку!!!!! Очень нужно, срочно!!! Программа перебора всех возможных подмножеств множества...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru