Я обнаружил, что с помощью рекурсивной функции не было хорошо для большого длины и целые числа, потому что он переваривает слишком много ОЗУ, а использование генератора/возобновляемой функции (что дает значения) было слишком медленным и требовало большой библиотеки, чтобы сделать ее кросс-платформенной.
Так вот нерекурсивно решения в C++, который производит разделы в упорядоченном (который идеально подходит для перестановок тоже). Я обнаружил, что это более чем в 10 раз быстрее, чем кажущиеся умными и сжатыми рекурсивными решениями, которые я пробовал для длин разделов 4 или более, но для длин 1-3 производительность не всегда лучше (и меня не волнует короткий длины, потому что они бывают быстрыми темпами).
// Inputs
unsigned short myInt = 10;
unsigned short len = 3;
// Partition variables.
vector<unsigned short> partition(len);
unsigned short last = len - 1;
unsigned short penult = last - 1;
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3.
unsigned short sum = 0;
// Prefill partition with 0.
fill(partition.begin(), partition.end(), 0);
do {
// Calculate remainder.
partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints.
/*
*
* DO SOMETHING WITH "partition" HERE.
*
*/
if (partition[cur + 1] <= partition[cur] + 1) {
do {
cur--;
} while (
cur > 0 &&
accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt
);
// Escape if seeked behind too far.
// I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3.
if (cur < 0) {
break;
}
// Increment the new cur position.
sum++;
partition[cur]++;
// The value in each position must be at least as large as the
// value in the previous position.
for (unsigned short i = cur + 1; i < last; ++i) {
sum = sum - partition[i] + partition[i - 1];
partition[i] = partition[i - 1];
}
// Reset cur for next time.
cur = penult;
}
else {
sum++;
partition[penult]++;
}
} while (myInt - sum >= partition[penult]);
Где я написал СДЕЛАТЬ ЧТО-ТО С «раздела» ЗДЕСЬ. - это то место, где вы действительно потребляете ценность. (На последней итерации код будет продолжать выполнять оставшуюся часть цикла, но я нашел, что это лучше, чем постоянно проверяя условие выхода - она оптимизирована для больших операций)
0,0,10
0,1,9
0,2,8
0,3,7
0,4,6
0,5,5
1,1,8
1,2,7
1,3,6
1,4,5
2,2,6
2,3,5
2,4,4
3,3,4
Oh I» ve использовал «unsigned short», потому что я знаю, что моя длина и целое не превысят определенных пределов, измените это, если оно вам не подходит :) Проверьте комментарии; одна переменная там (cur) должна была быть подписана для обработки длин 1 или 2, и есть соответствующий if-statement, который идет с этим, и я также отметил в комментарии, что если ваш вектор перегородки подписал ints, есть еще одна строка которые могут быть упрощены.
Чтобы получить все композиции, в C++ Я хотел бы использовать эту простую стратегию перестановки, которая, к счастью, не производит никаких дубликатов:
do {
// Your code goes here.
} while (next_permutation(partition.begin(), partition.end()));
гнезда, что в СДЕЛАТЬ ЧТО-ТО С «раздела» ЗДЕСЬ места, и вам хорошо идти.
Альтернативой поиску композиций (на основе кода Java здесь https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) является следующее. Я нашел, что это работает лучше, чем next_permutation().
// Process lexicographic permutations of partition (compositions).
composition = partition;
do {
// Your code goes here.
// Find longest non-increasing suffix
i = last;
while (i > 0 && composition[i - 1] >= composition[i]) {
--i;
}
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0) {
break;
}
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
j = last;
while (composition[j] <= composition[i - 1])
--j;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
temp = composition[i - 1];
composition[i - 1] = composition[j];
composition[j] = temp;
// Reverse the suffix
j = last;
while (i < j) {
temp = composition[i];
composition[i] = composition[j];
composition[j] = temp;
++i;
--j;
}
} while (true);
Вы заметите некоторые необъявленных переменных там, просто объявить их в начале кода перед всеми вашими сделай петли: i, j, pos и temp (неподписанные шорты) и composition (того же типа и длины как partition). Вы можете повторно использовать объявление i для его использования в цикле for в фрагменте кода разделов. Также обратите внимание на переменные, например last, которые предполагают, что этот код вложен в код разделов, указанный ранее.
Снова «Твой код идет здесь», где вы потребляете композицию для своих целей.
Для справки приведены мои заголовки.
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;
Несмотря на огромный рост скорости, используя эти подходы, для любых значительных чисел и длины разделов это все равно заставит вас с ума в вашем CPU :)
В случае, если не перестановками (2, 1, 1) быть в этом списке? –
Я знал, что кое-что забыл. Спасибо, добавлено. – deleted77
Разрешения целых разделов называются «композициями». –