Более эффективный способ для моей программы написать каждую миллиардную комбинацию?

Поэтому следующая программа генерирует комбинации по символам в этой главной строке, которую вы увидите в программе. Сначала программа генерирует все 48 из 12 выбранных комбинаций, а затем до 48 выбирает 19.

Проблема в том, что общее количество комбинаций составляет 65 триллионов, что невозможно вычислить за разумное время. Я подумал: «Хорошо, я просто напишу каждый миллиардный файл в файл». Что ж, это также займет уйму времени, потому что программа все равно должна считать до 65 триллионов, даже если она записывает только каждую миллиардную комбинацию.

Есть ли что-нибудь, что я мог бы изменить в своей программе, чтобы избежать необходимости учитывать чрезвычайно большое число, но при этом записывать каждую миллиардную комбинацию в файл?

#include <iostream>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}

unsigned long long count = 0;

int main()
{
ofstream myfile;
myfile.open ("m = 8.txt");

string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop";

for (int i = 12; i <= 19; i++)
{
std::size_t comb_size = i;

do
{
if (count == 0)
myfile << std::string(s.begin(),s.begin() + comb_size) << std::endl;

if (++count % 1000000000 == 0)
myfile << std::string(s.begin(),s.begin() + comb_size) << std::endl;

}while(next_combination(s.begin(),s.begin()+ comb_size,s.end()));
}

myfile.close();

cout << "Done!" << endl;

system("PAUSE");
return 0;
}

7

Решение

У меня есть простое преобразование, чтобы использовать другую библиотеку, которая примерно в 36 раз быстрее вашей. Это все еще грубая сила. Но, по оценкам, на моем компьютере ваш код займет 418 дней, а мой код — всего 3,65 дня. Все еще возмутительно долго. Но это приводит к длинным выходным.

Вот мой код:

#include <iostream>
#include <string>
#include <fstream>
#include "../combinations/combinations"
using namespace std;

unsigned long long count = 0;

int main()
{
ofstream myfile("m = 8.txt");

string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop";

for (int i = 12; i <= 19; i++)
for_each_combination(s.begin(), s.begin() + i, s.end(),
[&](std::string::const_iterator f, std::string::const_iterator l) -> bool
{
if (::count++ % 1000000000 == 0)
myfile << std::string(f, l) << std::endl;
return false;
});

myfile.close();

cout << "Done!" << endl;
return 0;
}

Сокращение количества испытаний на count во внутреннем цикле было увеличение производительности на 15%.

«../combination/combination» относится к этой библиотеке:

http://howardhinnant.github.io/combinations.html

Ссылка включает описание и полный исходный код.

Эта тестовая программа также может быть легко изменена для подсчета общего количества комбинаций:

#include <iostream>
#include <string>
#include "../combinations/combinations"
using namespace std;int main()
{
string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop";
unsigned long long count = 0;
for (int i = 12; i <= 19; i++)
count += count_each_combination(s.begin(), s.begin() + i, s.end());

cout << "Done! " << count << endl;
return 0;
}

какие выводы:

Done! 27189132782091

Код с открытым исходным кодом с лицензией Boost (он не является частью библиотеки Boost). Не стесняйтесь использовать его.

4

Другие решения

Это код, который я написал ранее для нахождения k-й перестановки данной строки. Я думаю, что моя идея похожа на @Tarik, что нам не нужно перечислять все перестановки до kth.

string getPermutation(string s, int k) {
string res;
int n = s.size();
int total = 1, digits = n - 1;
for (int i = 1; i < n; ++i)
total *= i;
while (res.size() < n)
{
int i = 0;
for (int m = 1; m < (int) ceil(k * 1.0 / total); ++m)
i++;
res += s[i];
s.erase(s.begin() + i); // erase from string is not a good idea:)
k = (k % total == 0) ? total : k % total;
total = (total == 1) ? 1 : total / digits--;
}
return res;
}

Это хорошо работает для короткой струны. Например getPermutation("12345", 37) вернусь 24135,

Но для вашей строки s с длиной 48переменная total переполнится даже с типом long long, Поэтому нам нужно проделать дополнительную работу, чтобы справиться с этим.

Мой код несколько сложен для понимания 🙂 Вы можете улучшить мой код. Я надеюсь, что это поможет вам.

UPDADE: Я понимаю, что вам нужно сочетание не перестановка. Я полностью ошибся! Забудь мой код 🙂

2

Есть способ получить доступ к k-индексам из ранга без необходимости перебирать все предыдущие. Я открыл и опубликовал эту технику пару лет назад. Итак, если все, что вы хотите сделать, это распечатать каждую миллиардную комбинацию, то класс, который я написал, делает это почти тривиальным, и не должно занимать более нескольких секунд, чтобы вычислить все комбинации для 27+ триллионов комбинаций, к которым обращаются с интервалами 1000000000. 27 трлн / 1 млрд = примерно 27 000 комбинаций, которые нужно будет распечатать.

Класс написан на C # для обработки общих функций для работы с биномиальным коэффициентом. Он выполняет следующие задачи:

  1. Выводит все K-индексы в хорошем формате для любого N, выбирают K в файл. K-индексы могут быть заменены более описательными строками или буквами.

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

  3. Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы. Используемая техника также намного быстрее, чем старые итеративные решения.

  4. Пользы Марк Доминус метод для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполнится и работает с большими числами.

  5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать, чтобы использовать 4 вышеуказанных метода. Методы доступа предоставляются для доступа к таблице.

  6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован во многих случаях, и нет известных ошибок. Класс использует математические отношения, которые можно увидеть из треугольника Паскаля, чтобы достичь эффективного способа перевода ранга и K-индексов.

Чтобы прочитать об этом классе и скачать код, см. Таблицы биномиального коэффициента.

Следующий проверенный пример кода будет перебирать каждую уникальную комбинацию:

public void Test10Choose5()
{
String S;
int Loop;
int N = 10;  // Total number of elements in the set.
int K = 5;  // Total number of elements in each group.
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
// The Kindexes array specifies the indexes for a lexigraphic element.
int[] KIndexes = new int[K];
StringBuilder SB = new StringBuilder();
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
// Get the k-indexes for this combination.
BC.GetKIndexes(Combo, KIndexes);
// Verify that the Kindexes returned can be used to retrive the
// rank or lexigraphic order of the KIndexes in the table.
int Val = BC.GetIndex(true, KIndexes);
if (Val != Combo)
{
S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
Console.WriteLine(S);
}
SB.Remove(0, SB.Length);
for (Loop = 0; Loop < K; Loop++)
{
SB.Append(KIndexes[Loop].ToString());
if (Loop < K - 1)
SB.Append(" ");
}
S = "KIndexes = " + SB.ToString();
Console.WriteLine(S);
}
}

Вам нужно будет перенести класс BinCoeff на C ++ и использовать в нем longs вместо int. Ваше приложение будет иметь как минимум 2 цикла. Внешний цикл создаст объект BinCoeff для каждого случая N выбора K. Внутренний цикл увеличит длинное значение на миллиард и вызовет метод BinCoeff.GetKIndexes, который вернет комбинацию, подходящую для печати. Возвращаемая комбинация имеет вид массива (int / long) с нулями. Вы можете создать другой массив символов или строки, которые могут быть проиндексированы значениями, возвращаемыми GetKIndexes.

Если вам нужны числа, превышающие то, что может содержать длинное значение, вы, вероятно, захотите изменить класс для использования класса BigInteger.

Спасибо за ссылку на калькулятор Wolfram Alpha. Можно найти лучший калькулятор биномиальных коэффициентов, который я нашел ранее, который работает с очень большими числами (он точно рассчитал случай, который дал в результате более 15 000 цифр в результате) Вот

1

От http://en.wikipedia.org/wiki/Combinadic Существует алгоритм для непосредственного вычисления k-й комбинации. Вы должны сначала сохранить треугольник Паскаля. Если вам нужен пример кода, вы можете взглянуть на (язык Python) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py.

1

Вы можете использовать битвектор для ускорения некоторых вычислений, адаптированных из перевернутые страницы шахматного программирования Wiki.

#include <iostream>
#include <iomanip>
#include <cstdint>

using U64 = uint64_t;

// generate the next integer with the same number of bits as c
U64 next_combination(U64 c)
{
auto const smallest = c & -c;
auto const ripple = c + smallest;
auto ones = c ^ ripple;
ones = (ones >> 2) / smallest;
return ripple | ones;
}

// generate all integers with k of the first n bits set
template<class Function>
void for_each_combination(std::size_t n, std::size_t k, Function fun)
{
U64 y;
auto const n_mask = (1ULL << n) - 1; // mask with all n bits set to 1
auto const k_mask = (1ULL << k) - 1; // mask with first k bits set to 1

auto x = k_mask; fun(x);
for (; (y = next_combination(x) & n_mask) > x; x = y) fun(y);
}

int main()
{
auto const million = 1000000ULL;
auto count = U64 { 0 };
for (auto i = 12; i < 20; ++i) {
for_each_combination(48, i, [&](U64 c) {
/*if (count++ & million == 0) std::cout << std::dec << std::setfill(' ') << std::setw(8) << (count - 1) / million << ": " << std::hex << std::showbase << std::setfill('0') << std::setw(16) << c << "\n";*/
++count;
});
}
std::cout << count << "\n";
}

На одном ядре внутри виртуальной коробки моего Xeon E5-1650 @ 3,2 ГГц моя лучшая оценка состоит в том, что потребуется 3,52 дня, чтобы увеличить счетчик в 2,7e13 раз (не генерируя сам вывод). Это работает только для подмножеств B (n, k) с n < 64, если вы не используете некоторый 128-битный целочисленный класс.

Учитывая битвектор, который имеет k снаружи n биты, установленные в 1, очень просто сопоставить с исходной последовательностью символов или любым другим типом и вывести любую требуемую комбинацию. Для последовательностей, которые не имеют случайного доступа к итераторам, это, конечно, дороже, чем подход Говарда Хиннанта.

1

если вам все равно, каково действительное число, вы используете 32-битное целое число, которое все равно сообщит вам, что вы набрали 1 миллиард.

-1
А ты уже прошел курс программирования? Супер скидка!
Прокачать скилл $$$
×