Код, который использует итеративный интерфейс. Временная сложность O (n ^ 2), Пространственная сложность имеет накладные расходы: копия n (log n битов), итерационная переменная (log n битов), отслеживание ni (log n битов), копия текущего значения (log n битов), копия p (n log n битов), создание следующего значения (log n битов) и набор битов используемых значений (n битов). Вы не можете избежать накладных расходов из n log n битов. По времени это также O (n ^ 2) для установки битов. Это можно немного уменьшить, но за счет использования декорированного дерева для хранения используемых значений.
Это может быть изменено, чтобы использовать произвольные целочисленные значения точности и наборы битов, вместо этого используя вызовы соответствующих библиотек, и вышеупомянутые границы будут фактически вступать в силу, а не ограничиваться при N = 8, переносимо такой же, как короткий, и такой же маленький, как 16 бит). 9! = 362880> 65536 = 2 ^ 16
#include <math.h>
#include <stdio.h>
typedef signed char index_t;
typedef unsigned int permutation;
static index_t permutation_next(index_t n, permutation p, index_t value)
{
permutation used = 0;
for (index_t i = 0; i < n; ++i) {
index_t left = n - i;
index_t digit = p % left;
p /= left;
for (index_t j = 0; j <= digit; ++j) {
if (used & (1 << j)) {
digit++;
}
}
used |= (1 << digit);
if (value == -1) {
return digit;
}
if (value == digit) {
value = -1;
}
}
/* value not found */
return -1;
}
static void dump_permutation(index_t n, permutation p)
{
index_t value = -1;
fputs("[", stdout);
value = permutation_next(n, p, value);
while (value != -1) {
printf("%d", value);
value = permutation_next(n, p, value);
if (value != -1) {
fputs(", ", stdout);
}
}
puts("]");
}
static int factorial(int n)
{
int prod = 1;
for (int i = 1; i <= n; ++i) {
prod *= i;
}
return prod;
}
int main(int argc, char **argv)
{
const index_t n = 4;
const permutation max = factorial(n);
for (permutation p = 0; p < max; ++p) {
dump_permutation(n, p);
}
}