VPF::Простой перебор n-числа переменных

Salatovec

Дата 14.12.2011, 21:24 (ссылка)

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

Загрузка ...

Бывалый

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

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

Доброго всем времени суток.

Подскажите, пожалуйста, как запрограммировать перебор всех комбинаций последовательности чисел, ну вот к пример:

дана последовательность чисел 1, 2 и 3. Комбинации этих чисел:

123
132
213
231
312
321

Такое маленькое количество комбинаций можно и вручную записать, конечно. А вот к примеру если чисел будет 8? Или 20?

Заранее огромное спасибо!

hawk3500

Дата 14.12.2011, 22:33 (ссылка)

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

Загрузка ...

Бывалый

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

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

http://progpage.narod.ru/alg/per.html

Google в помощь)

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

воин dzen'a

volatile

Дата 15.12.2011, 00:08 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

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

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

Вот такая наиогромнейшая программулина переберет все варианты smile

Код


int main()
{
   char str[] = "123"; //<= сюда добавить символы которые нужны
   do
      std::cout << str << std::endl;
   while (std::next_permutation( str, str+sizeof(str)-1));
}

http://liveworkspace.org/code/af6e49841df5...73e87b91412afad

Но осторожно. потому-что кол-во вариантов равно факториалу от кол-ва символов

Добавлено через 2 минуты и 36 секунд
да, чуть не забыл, символы должны быть отсторированы
ну или, просто поместите перед do

Код


std::sort (str, str+sizeof(str)-1);

Salatovec

Дата 15.12.2011, 20:52 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(hawk3500 @ 14.12.2011, 22:33

)

http://progpage.narod.ru/alg/per.html

Google в помощь)

Спасибо за ссылку, постараюсь разобраться)

Цитата(volatile @ 15.12.2011, 00:08

)

Вот такая наиогромнейшая программулина переберет все варианты
код C++

int main()
{
   char str[] = "123"; //<= сюда добавить символы которые нужны
   do
      std::cout << str << std::endl;
   while (std::next_permutation( str, str+sizeof(str)-1));
}
http://liveworkspace.org/code/af6e49841df5...73e87b91412afad

Но осторожно. потому-что кол-во вариантов равно факториалу от кол-ва символов

Добавлено через 2 минуты и 36 секунд
да, чуть не забыл, символы должны быть отсторированы
ну или, просто поместите перед do
код C++
1:
std::sort (str, str+sizeof(str)-1);

Спасибо, кода немного и всё поняно, разобрался. Один только вопрос - а что если в комбинации у меня присутствуют числа от 10 и выше? К пример 123456789'10'. Ведь алгоритм 10 распознает как 0 и 1. Как быть?

Это сообщение отредактировал(а) Salatovec - 15.12.2011, 20:54

newbee

Дата 15.12.2011, 20:55 (ссылка)

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

Загрузка ...

Бревно

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

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

Цитата(Salatovec @ 15.12.2011, 21:52

)

Ведь алгоритм 10 распознает как 0 и 1. Как быть?

Использовать массив чисел вместо массива букв.

Думаю, задача у тебя самому написать алгоритм перебора, а не воспользоваться стандартным готовым.

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

You're face to face
With man who sold the world

Salatovec

Дата 15.12.2011, 21:06 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(newbee @ 15.12.2011, 20:55

)

Цитата(Salatovec @ 15.12.2011, 21:52 )
Ведь алгоритм 10 распознает как 0 и 1. Как быть?
Использовать массив чисел вместо массива букв.

Думаю, задача у тебя самому написать алгоритм перебора, а не воспользоваться стандартным готовым.

Задача именно перебрать, а уж как - неважно...

volatile

Дата 15.12.2011, 23:47 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

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

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

http://liveworkspace.org/code/b170527b515c...6b3ab9ef0cac358

Qu1nt

Дата 16.12.2011, 12:11 (ссылка)

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

Загрузка ...

Опытный

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

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

С использованием C++11.

Код


#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

int main()
{
    vector<int> data { 10, 20, 30 };   
    sort(begin(data), end(data));
    do
    {
        copy(begin(data), end(data), ostream_iterator<int>(cout << endl, " "));
    } while (next_permutation(begin(data), end(data)));
}

Это сообщение отредактировал(а) Qu1nt - 16.12.2011, 12:18

Salatovec

Дата 17.12.2011, 00:06 (ссылка)

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

Загрузка ...

Бывалый

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

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

Спасибо всем за помощь огромное! Ответили по факту, даже более чем smile

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