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

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

Форум программистов > C/C++: Общие вопросы > Полный перебор

Автор: Веталька 30.1.2010, 17:28

появилась потребность перебрать массив из 7 элементов (1,2,3,4,5,6,7), нужно получить все варианты, но в количестве 1 штука, то есть
1 2 3 4 5 6 7 12 13 14 15 16 17 21 22 23 24 25 26 27 31.....1234567.....7777777, и замечание элемент 12 = 21, 13=31....2 = 22, 2=222, элементы после запуска цикла будут один на второго накладываться, поэтому те которые повторяются можно вычеркнуть (разумеется один все таки нужно оставить)

пробовал сделать цикл в цикле(и так семь штук), но столкнулся с проблемой, количество переборов равно 7^7, а это очень не выгодно, так как комбинаций без повтора всего 7^2 = 128, что можете посоветовать?

Автор: mes 30.1.2010, 17:51

Цитата(Веталька @ 30.1.2010, 16:28

)

7^2 = 128,

может 2^7 ?

Цитата(Веталька @ 30.1.2010, 16:28

)

появилась потребность перебрать массив из 7 элементов

очередность вывода имеет значение ?

Добавлено через 6 минут и 38 секунд
вообщем ловите и допиливайте напильником под свои нужды :

Код


#include <iostream>

int arr[] = { 1,2,3,4,5,6,7 };
const size_t arr_len = sizeof (arr) /sizeof(*arr);

int main ()
{
    for (size_t i=0; i < (1 << arr_len); ++i)
    {
        unsigned value = 0;

        for (size_t j=0; j<arr_len; ++j)
          if ( (i>>j) & 1 )
          {
             value *=10;             
             value += arr[j];
          }
        
          std::cout << value << " ("<< i << "), "; 
    }
}

Автор: Веталька 30.1.2010, 21:52

mes, спасибо, то что искал smile

, не могли бы вы еще немножко принцип перебора объяснить?

Автор: Веталька 30.1.2010, 23:06

может ктото чтото попроще предложет, этот способ слишком заумный для меня smile

Автор: Dov 30.1.2010, 23:51

Рекурсия подойдёт?
Коряво, правда, написал. Но, вроде, работает. Если что, сам подправишь, где нужно..

Код

void findSolution(char * buf, char * arr, int len, int k, int i = 0)
{
    if(k < 1)
    {
        for(int j = 0; j < len; j++)
            cout << buf[j];
        cout << endl;
        return;
    }

    int n = strlen(arr) + 1;
    for(int j = i; j < n - k; j++)
    {
        buf[len - k] = arr[j];
        findSolution(buf, arr, len, k - 1, j + 1);
    }    
}

int main()
{
    char   str[] = "1234567";
    char * p     = str;
    char   buf[8];

    while(*p++)
        findSolution(buf, str, p - str, p - str);

    return 0;
}

Автор: Веталька 31.1.2010, 00:19

mes, Dov, спасибо за помощь, вопрос решен smile

Автор: artsb 31.1.2010, 00:24

Цитата(Веталька @ 30.1.2010, 23:06

)

этот способ слишком заумный для меня

А если "расшифровать" его?

Код


#include <iostream>
#include <math> // для pow
int arr[] = { 1,2,3,4,5,6,7 };
// расчёт кол-ва элементов в массиве
const size_t arr_len = sizeof (arr) /sizeof(*arr);
int main ()
{
    for (size_t i=0; i < ((int)pow(2, arr_len)); ++i)
    {
        unsigned value = 0;
        for (size_t j=0; j<arr_len; ++j)
        // каждый сдвиг вправо равносилен делению на 2, а операторы "& 1" производят проверку числа на нечётность
          if ( (i/((int)pow(2, j))) % 2 )
          {
             value *=10;             
             value += arr[j];
          }
        
          std::cout << value << " ("<< i << "), "; 
    }
}

Автор: mes 31.1.2010, 11:28

В общем происходит так - Просто перебираются все значения от нуля до 1<<arr_len (аналогично 2^arr_len, т.е 2^7 для нашего случая)
потом из битового представления значения итерации строится число, заменяя единичные биты на соответствующий ему элемент массива..
для десятичного сдвига используются *10 и сдвиг происходит только при установленном бите, чтоб не было позиций с нулем в результативном числе.

. например 11 итерация
7,6,5,4,3,2,1 // наш массив справа налево, т.е индекс 0 справа
0 0 0 1 0 1 1 // 11 в битовом представлении
0 0 0 3 0 2 1 // позиция в результативном числе (слева направа),

итого
((1*10)+2*10)*4 = 124 // еще есть 0*10, но это издержка, которая ни на что не влияет.

smile

Автор: zim22 31.1.2010, 11:43

Цитата(Веталька @ 30.1.2010, 16:28

)

появилась потребность перебрать массив из 7 элементов

std::next_permutation?

Автор: mes 31.1.2010, 11:57

Цитата(zim22 @ 31.1.2010, 10:43

)

std::next_permutation?

не подходит, так как

Цитата(Веталька @ 30.1.2010, 16:28

)

нужно получить все варианты, но в количестве 1 штука...
замечание элемент 12 = 21, 13=31....2 = 22, 2=222,

Автор: zim22 31.1.2010, 12:44

Веталька, то, что ты хотел найти - называется сочетания без повторений.
их количество вычисляется по формуле n! / (n - k)! * k!
n - размер множества, k - размер выборки

Цитата(mes @ 31.1.2010, 10:57

)

не подходит, так как

тогда подойдёт алгоритм http://photon.poly.edu/~hbr/boost/combinations.html#next_combin_desc, который является кандидатом на включение в буст

Код


#include "stdafx.h"
#include <iostream>
#include <vector>

#include "combination.hpp"
using namespace boost;

int main ()
{
 const int r = 2; // количество элементов, которое будет взято из множества
 int arr[] = {1, 2, 3, 4, 5, 6, 7};
 const int n = sizeof(arr) / sizeof(*arr);
 std::vector<int> v_int(arr, arr + n); 

 int N = 0;
 do {
     ++N;
     if (N < 10 || N > 117) {
         std::cout << "[ " << v_int[0];
         for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
         std::cout << " ]" << std::endl;
     } else if (N == 10) {
         std::cout << "  . . ." << std::endl;
     }
 } while (next_combination(v_int.begin(), v_int.begin() + r, v_int.end()));
 std::cout << "Found " << N << " combinations of size " << r << " without repetitions"
           << " from a set of " << n << " elements." << std::endl;
}

Автор: mes 31.1.2010, 15:31

Цитата(artsb @ 30.1.2010, 23:24

)

     for (size_t j=0; j<arr_len; ++j)
        // каждый сдвиг вправо равносилен делению на 2, а операторы "& 1" производят проверку числа на нечётность
          if ( (i/((int)pow(2, j))) % 2 )
          {
             value *=10;
             value += arr[j];
          }

тогда уж уж лучше так :

Код


       for (size_t j=0, k=i; k; k/=2, ++j)
          if ( k % 2 )
          {
             value *=10;             
             value += arr[j];
          }

Автор: artsb 31.1.2010, 15:42

Цитата(mes @ 31.1.2010, 15:31

)

тогда уж уж лучше так :

Ага. Так действительно лучше, проще и без вызова функции.
Я просто даже не жумал о том как можно оптимизировать, просто переписал в более "понятный" вид, так сказать. smile

Автор: Лешкин 31.1.2010, 21:47

А если мне нужно сделать перебор только по три элемента с этого же множества?

Добавлено через 2 минуты и 11 секунд
З.Ы.
С последующей передачей этих переборов в другую функцию...

Автор: Веталька 31.1.2010, 23:56

Цитата

А если мне нужно сделать перебор только по три элемента с этого же множества?

Добавлено через 2 минуты и 11 секунд
З.Ы.
С последующей передачей этих переборов в другую функцию...

тебе любые 3 нужно??? или именно для 3х элементов?
http://cplusplus.com/reference/algorithm/prev_permutation/ подойдет???

Автор: Лешкин 1.2.2010, 23:08

Цитата

это подойдет???

Нет! Мне нужно сделать перебор (допустим) из семи элементов в одном случае по два элемента, в другом по три и т.п. и передавать результат перебора на каждой итерации в функцию...

Автор: zim22 2.2.2010, 12:17

Лешкин, для начала сформулируй что именно тебе нужно.
http://ru.wikipedia.org/wiki/Размещение
или
http://ru.wikipedia.org/wiki/Сочетание