VPF::Полный перебор - Форум программистов

Веталька

Дата 30.1.2010, 17:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

появилась потребность перебрать массив из 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 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(Веталька @ 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 << "), "; 
    }
}

--------------------

http://opendots.net

Веталька

Дата 30.1.2010, 21:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

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

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

--------------------

Ради зачета студент идет на все, даже на лекции........................

Веталька

Дата 30.1.2010, 23:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

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

--------------------

Ради зачета студент идет на все, даже на лекции........................

Dov

Дата 30.1.2010, 23:51 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 15
Всего: 88

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

Код

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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

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

--------------------

Ради зачета студент идет на все, даже на лекции........................

artsb

Дата 31.1.2010, 00:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2280
Регистрация: 17.7.2007
Где: центр Вселенной

Репутация: 1
Всего: 64

Цитата(Веталька @ 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 << "), "; 
    }
}

Это сообщение отредактировал(а) artsb - 31.1.2010, 00:47

--------------------

Чем отличается умный человек от мудрого?
Умный - выпутается из любой ситуации.
Мудрый - просто в неё не попадёт.

mes

Дата 31.1.2010, 11:28 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

В общем происходит так - Просто перебираются все значения от нуля до 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

Это сообщение отредактировал(а) mes - 31.1.2010, 11:29

--------------------

http://opendots.net

zim22

Дата 31.1.2010, 11:43 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

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

)

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

std::next_permutation?

Это сообщение отредактировал(а) zim22 - 31.1.2010, 11:54

--------------------

C++ FAQ Lite

mes

Дата 31.1.2010, 11:57 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

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

)

std::next_permutation?

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

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

)

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

--------------------

http://opendots.net

zim22

Дата 31.1.2010, 12:44 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

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

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

)

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

тогда подойдёт алгоритм next_combination, который является кандидатом на включение в буст

Код


#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;
}

Это сообщение отредактировал(а) zim22 - 31.1.2010, 12:47

--------------------

C++ FAQ Lite

mes

Дата 31.1.2010, 15:31 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(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];
          }

--------------------

http://opendots.net

artsb

Дата 31.1.2010, 15:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2280
Регистрация: 17.7.2007
Где: центр Вселенной

Репутация: 1
Всего: 64

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

)

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

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

--------------------

Лешкин

Дата 31.1.2010, 21:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 24.1.2010

Репутация: 1
Всего: 1

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

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

Веталька

Дата 31.1.2010, 23:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

Цитата

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

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

тебе любые 3 нужно??? или именно для 3х элементов?
это подойдет???

--------------------

Ради зачета студент идет на все, даже на лекции........................

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »