Алгоритм генерации всех комбинаций

@tdo22 · Регистрация: 14.02.2013

Author24 — интернет-сервис помощи студентам

Здравствуйте, есть массив типа int, размер 256
в каждой ячейке цифра от 1 до 4.
Нужен быстрый алгоритм который запишет в текстовый файл .txt все комбинации этих чисел.
Может у есть такой ?

@castaway · 02.02.2015, 20:28

Алгоритм перебора для записи в файл? Я всё правильно понял? Или всё-таки переформулируешь свой вопрос!?

@tdo22 · 02.02.2015, 20:31 **[ТС]**

Алгоритм для перебора всех комбинаций из данных чисел в массиве, как-то так.
Но проблема в том, что массив большой - 256 символов, и перебор идет очень медленно.

@RaiaNKnight · 02.02.2015, 20:37

1) Генерировать только уникальные комбинации?
2) Комбинации должны быть длиной 256 символов?

Байт · 02.02.2015, 20:40

Сообщение от tdo22

и перебор идет очень медленно.

4²⁵⁶ вариантов. Ну и чего ты хочешь?
Можно уменьшить время генерации каждой комбинации линейно. (Зависит от того как ты перебираешь) Скажем, в 10 раз. Но все равно все 2⁵¹² комбинаций придется выводить. И где ты найдешь диск, на который поместится 10¹⁵⁰ записей по 256 байт? Даже если объединить все ресурсы интернета, такой емкости тебе не найти. Это "немножко" больше количества атомов во вселенной

@castaway · 02.02.2015, 21:44

Я тут даже наглядный эксперимент провёл...
Размер массива 18 --- 9 262 693 440 байт в файле.
Размер массива 19 --- 37 153 692 576 байт в файле.
Размер массива 20 --- 195 545 750 400 байт в файле.
...
Дальше размера массива 20 заходить не хочу, т.к. это очень долгий процесс...
Хочешь - проверь сам.

Кликните здесь для просмотра всего текста

C++

#include <cstdio>
#include <cstdint>
#include <algorithm>
 
int main()
{
    uint64_t        n = 0;
    int             arr[10];
    const size_t    size = sizeof( arr ) / sizeof( arr[0] );
 
    // fill array
    for ( int & i : arr ) {
        i = rand() % 4 + 1; // from 1 to 4 inclusive
    }
 
    // sort it for 'next_permutation' algo. ...
    std::sort( &arr[0], &arr[size] );
 
    do {
        ++n;
    } while ( std::next_permutation( &arr[0], &arr[size] ) );
    printf( "Output file size: %llu\n", n * size );
}

Байт · 02.02.2015, 22:09

Не по теме:

Сообщение от castaway

Я тут даже наглядный эксперимент провёл...

Ага, значит на слово старой таксе не поверил?:D

Добавлено через 8 минут

Не по теме:

Совсем не по теме, но любопытно... Как трактовать приставку ЭКС в слове ЭКСпотенциальный? Бывшая потенция (возможность) ?

@castaway · 02.02.2015, 22:16

Не по теме:

Сообщение от Байт

Ага, значит на слово старой таксе не поверил?:)

Ну почему не поверил, просто захотел привести наглядный пример:)
Если вопрос про "ЭКС" ко мне, то я не понял)

Байт · 02.02.2015, 22:22

Не по теме:

Сообщение от castaway

Если вопрос про "ЭКС" ко мне, то я не понял)

И не к тебе, и вообще музыкой навеяло из другого топика. Просто вот в голову тюкнул такой вопрос. Ведь тысячи раз это слово произносил, и никогда не думал об этимологии.
Надеюсь, никого ненароком не задел?:)

Croessmah · 03.02.2015, 04:45

Не по теме:

Сообщение от Байт

ЭКСпотенциальный?

экспоненциальный. Всё-таки экспонент, а не экспотент :D

Сообщение от Байт

Ведь тысячи раз это слово произносил

Прям вот с буквой "т"? :)

Сообщение от Байт

Как трактовать приставку ЭКС

экс - это часть корня, а не приставка.
Мысля:
e^x - e в степени икс, сокращенно "екс", для удобства преобразовали в "экс" :D

Байт · 03.02.2015, 10:48

Не по теме:

Сообщение от Croessmah

Прям вот с буквой "т"?

Понял. Стыдно стало...:cry:
Век учись...

@tdo22 14 / 14 / 13 Регистрация: 14.02.2013 Сообщений: 787
		1
	Алгоритм генерации всех комбинаций 02.02.2015, 20:13. Показов 3492. Ответов 10 Метки нет (Все метки) Здравствуйте, есть массив типа int, размер 256 в каждой ячейке цифра от 1 до 4. Нужен быстрый алгоритм который запишет в текстовый файл .txt все комбинации этих чисел. Может у есть такой ? 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	02.02.2015, 20:28	2
	Алгоритм перебора для записи в файл? Я всё правильно понял? Или всё-таки переформулируешь свой вопрос!? 0

@tdo22 14 / 14 / 13 Регистрация: 14.02.2013 Сообщений: 787
	02.02.2015, 20:31 [ТС]	3
	Алгоритм для перебора всех комбинаций из данных чисел в массиве, как-то так. Но проблема в том, что массив большой - 256 символов, и перебор идет очень медленно. 0

@RaiaNKnight 97 / 71 / 12 Регистрация: 29.06.2011 Сообщений: 465 Записей в блоге: 1
	02.02.2015, 20:37	4
	1) Генерировать только уникальные комбинации? 2) Комбинации должны быть длиной 256 символов? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	02.02.2015, 20:40	5
	Сообщение от tdo22 и перебор идет очень медленно. 4²⁵⁶ вариантов. Ну и чего ты хочешь? Можно уменьшить время генерации каждой комбинации линейно. (Зависит от того как ты перебираешь) Скажем, в 10 раз. Но все равно все 2⁵¹² комбинаций придется выводить. И где ты найдешь диск, на который поместится 10¹⁵⁰ записей по 256 байт? Даже если объединить все ресурсы интернета, такой емкости тебе не найти. Это "немножко" больше количества атомов во вселенной 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	02.02.2015, 22:09	7
	Не по теме: Сообщение от castaway Я тут даже наглядный эксперимент провёл... Ага, значит на слово старой таксе не поверил?:D Добавлено через 8 минут Не по теме: Совсем не по теме, но любопытно... Как трактовать приставку ЭКС в слове ЭКСпотенциальный? Бывшая потенция (возможность) ? 0

@castaway
	02.02.2015, 22:16 #8
	Не по теме: Сообщение от Байт Ага, значит на слово старой таксе не поверил?:) Ну почему не поверил, просто захотел привести наглядный пример:) Если вопрос про "ЭКС" ко мне, то я не понял) 0

Байт
	02.02.2015, 22:22 #9
	Не по теме: Сообщение от castaway Если вопрос про "ЭКС" ко мне, то я не понял) И не к тебе, и вообще музыкой навеяло из другого топика. Просто вот в голову тюкнул такой вопрос. Ведь тысячи раз это слово произносил, и никогда не думал об этимологии. Надеюсь, никого ненароком не задел?:) 0

Croessmah
	03.02.2015, 04:45 #10
	Не по теме: Сообщение от Байт ЭКСпотенциальный? экспоненциальный. Всё-таки экспонент, а не экспотент :D Сообщение от Байт Ведь тысячи раз это слово произносил Прям вот с буквой "т"? :) Сообщение от Байт Как трактовать приставку ЭКС экс - это часть корня, а не приставка. Мысля: e^x - e в степени икс, сокращенно "екс", для удобства преобразовали в "экс" :D 0

Байт
	03.02.2015, 10:48 Алгоритм генерации всех комбинаций #11
	Не по теме: Сообщение от Croessmah Прям вот с буквой "т"? Понял. Стыдно стало...:cry: Век учись... 0

Опции темы