Генерация n-значных чисел, упорядоченных по сумме отдельных цифр (без рекурсии)
-
19-09-2019 - |
Вопрос
Я хочу сгенерировать все возможные значения n-значного числа в следующем порядке, где последовательность определяется суммой отдельных цифр.
Например, с n = 3
:
111 sum = 3
112 sum = 4
121
211
122 sum = 5
212
221
113
131
311
114 sum = 6
141
411
:::
999 sum = 27
Порядок внутри группы сумм не важен.
Любая помощь, идеи будут оценены по достоинству
Решение
Ты можешь всегда превратите рекурсивную задачу в итеративную, если вы поддерживаете свой собственный стек важных данных - это если причина избегания рекурсии состоит в том, что язык ее не поддерживает.
Но если язык делает поддержите его, тогда рекурсивные решения будут гораздо более элегантными.
Единственная другая причина, по которой я могу избежать рекурсии, — это ограниченная глубина стека.В этом случае итеративное преобразование рекурсивного решения смягчит проблему, поскольку не потребует столько места в стеке.
Но нужно понимать, что глубина стека для обработки n чисел растёт только относительно log10н.Другими словами, вы получаете только дополнительный кадр стека на каждую цифру (только 10 кадров стека для обработки всего диапазона 32-битных целых чисел).
В стороне: к тому времени, как вы доберетесь до этой точки, ваш алгоритм будет работать так долго, что кадры стека будут наименьшей из ваших проблем :-)
Вот рекурсивное решение Python:
def recur (numdigits,sum,pref="",prefsum=0):
if numdigits == 0:
if prefsum == sum:
print "%s, sum=%d"%(pref,prefsum)
else:
for i in range (1,10):
recur (numdigits-1,sum,"%s%d"%(pref,i),prefsum+i)
def do (n):
for i in range (1,n*9+1):
recur (n,i)
do (2)
do (3)
какие выходы (для 2 и 3):
11, sum=2 111, sum=3
12, sum=3 112, sum=4
21, sum=3 121, sum=4
13, sum=4 211, sum=4
22, sum=4 113, sum=5
31, sum=4 122, sum=5
14, sum=5 131, sum=5
23, sum=5 212, sum=5
32, sum=5 221, sum=5
41, sum=5 311, sum=5
15, sum=6 114, sum=6
: : : :
89, sum=17 989, sum=26
98, sum=17 998, sum=26
99, sum=18 999, sum=27
Имейте в виду, что решение все еще можно несколько оптимизировать — я оставил его в исходном виде, чтобы показать, насколько элегантной может быть рекурсия.Далее следует чисто итеративное решение, но я все же предпочитаю рекурсивное.
Запустите следующую программу и используйте sort
и awk
под UNIX, чтобы получить желаемый порядок.Например:
go | sort | awk '{print $2}'
Обратите внимание, что для сортировки используются внешние инструменты, но вы можете так же легко сортировать внутри кода C (если позволяет память).
#include <stdio.h>
int main (void) {
int i, sum, carry, size;
int *pDigit;
// Choose your desired size.
size = 2;
// Allocate and initialise digits.
if ((pDigit = malloc (size * sizeof (int))) == NULL) {
fprintf (stderr, "No memory\n");
return 1;
)
for (i = 0; i < size; i++)
pDigit[i] = 1;
// Loop until overflow.
carry = 0;
while (carry != 1) {
// Work out sum, then output it with number.
// Line is sssssssssssssssssss ddddd
// where sss...sss is the fixed-width sum, zero padded on left (for sort)
// and ddd...ddd is the actual number.
sum = 0;
for (i = 0; i < size; i++)
sum += pDigit[i];
printf ("%020d ", sum);
for (i = 0; i < size; i++)
printf ("%d", pDigit[i]);
printf ("\n");
// Advance to next number.
carry = 1;
for (i = 0; i < size; i++) {
pDigit[size-i-1] = pDigit[size-i-1] + carry;
if (pDigit[size-i-1] == 10)
pDigit[size-i-1] = 1;
else
carry = 0;
}
}
return 0;
}
Другие советы
Вы можете использовать std::next_permutation?
Функция Next_permution () пытается преобразовать заданный диапазон элементов [Start, End) в следующую лексикографически большую перестановку элементов.Если это удастся, он возвращает истину, в противном случае он возвращает ложь.
Если предоставлен строгий объект функции упорядочения CMP, он используется вместо <оператора при сравнении элементов.
Видеть это: предыдущий ответ ТАК
Если не имеет значения, какой шаблон вы используете, пока шаблон существует (из вашего сообщения не совсем ясно, имеете ли вы в виду конкретный шаблон), то для n = 3 начните с 111
и увеличивайте, пока не достигнете 999
.
Кстати, термин, обозначающий то, о чем вы просите, не совсем «перестановки».
Вы можете попытаться свести проблему к двум сегментам:
Два разделения сегментов просты:Начните со всех минус одного в ведре А и одного в ведре Б, затем поместите один из А в Б, пока в А не останется только один.
Тогда всего лишь три разделения ведра:Начните со всех минус двух в ведре A и по одному в B и C.Уменьшите A на один и соберите все два разделения ведра по три в B и C, повторяйте, пока A не будет содержать только один.