Плоские перестановки n-кортежа (ширина вначале)
Я хотел бы перечислить n-кортеж. Например, для n = 2:
00 01 10 11
02 20 12 21 22
03 30 13 31 23 32 33
04 40 14 41 ...
n = 3 начнется так:
000 001 010 100 011 101 110 111
002 020 200 012 102 021 120 201 210 112 121 211 122 212 221 222
003 ...
Порядок кортежей с одинаковыми элементами не важен (например, 001 и 010), но кортежи с более (011 против 001) или, что более важно, более крупными (002 против 001) элементами должны всегда появляться позже.
После некоторого поиска появилось много связанных алгоритмов, но ни одного специально для этого случая. Есть ли такой алгоритм?
Изменить: изображение случая n = 2. Зеленые линии обозначают элементы, которые достигаются путем перетасовки порядка элементов в кортеже.
Изменить: Разъяснение о заказе:
- Кортежи в основном отсортированы по максимальному элементу (152 > 444)
- Затем сортируются по второму по величине элементу (053 > 252) и т. Д. (12341 > 12340)
- Порядок среди кортежей с одинаковыми элементами произвольный (123 = 321)
5 ответов
Позволять seq(n, k) дать последовательность, которую вы хотите с k цифры на запись, с цифрами из 0 в n,
Пусть шаг i быть фазой, которая генерирует все кортежи, где максимальная цифра i,
На каждом этапе мы просто генерируем i+1-начальное представление всех чисел до (i+1) ** (k - 1) - 1 (т.е. до k-1 цифр). Для каждого i+1-начное представление, мы затем производим элементы последовательности, вставляя цифру i в каждом месте в i+1Представление
Чтобы избежать дубликатов, мы ломаемся рано в случае, если мы сталкиваемся с i уже в i+1Представление
Вот (уродливый!) Пример реализации в python:
def to_nary_string(num, n):
if num == 0:
return "0"
result = ""
while num != 0:
result = str(num % n) + result
num /= n
return result
def seq(n, k):
print "0" * k
for i in range(2, n+2):
for x in range(i**(k-1)):
stem = to_nary_string(x, i).zfill(k-1)
c = str(i-1)
for j in range(k):
print stem[:j] + c + stem[j:],
if j != k-1 and stem[j] == c:
break
print
РЕДАКТИРОВАТЬ: проблема с этим заключается в том, что k-1 Цифровые строки должны быть в том же порядке, что и кортежи, а не последовательные n-заказ Небольшое изменение функции дает желаемый результат:
# Original list and string version
def seq(n, k):
if (k == 0):
return [""]
result = []
for i in range(n+1):
c = str(hex(i))[2:] # 10 -> a, 11-> b, etc.
for subseq in seq(i, k-1):
for j in range(k):
result.append(subseq[:j] + c + subseq[j:])
if j != k-1 and subseq[j] == c:
break
return result
Также, благодаря Клавдиу, здесь есть версия генератора и кортежа
# Generator and tuple version
#
# Thanks Claudiu!
def seq(n, k):
if (k == 0):
yield ()
return
for i in range(n+1):
for subseq in seq(i, k-1):
for j in range(k):
yield subseq[:j] + (i,) + subseq[j:]
if j != k-1 and subseq[j] == i:
break
Результат (разрывы строк добавлены для ясности):
>>> for x in seq(4, 2):
print x,
00
10 01 11
20 02 21 12 22
30 03 31 13 32 23 33
40 04 41 14 42 24 43 34 44
>>> for x in seq(3, 3):
print x,
000
100 010 001
110 101 011
111
200 020 002
210 120 102 201 021 012
211 121 112
220 202 022
221 212 122
222
300 030 003
310 130 103 301 031 013
311 131 113
320 230 203 302 032 023
321 231 213 312 132 123
322 232 223
330 303 033
331 313 133
332 323 233
333
И быстрая проверка работоспособности:
>>> len(seq(12, 4)) == 13 ** 4
True
Хорошо, учитывая, что ваш n самое большее 4, и у вас есть только 13 элементов, это действительно лучший способ сделать это:
import itertools
alphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
def tup_sort_key(t):
largest_el = max(t)
z = list(t)
z.sort(reverse=True)
return tuple(z)
def gen_all_n_tuples(n):
all_els = list(itertools.product(*([alphabet]*n)))
all_els.sort(key=tup_sort_key)
return all_els
Краткое объяснение: создайте все возможные кортежи и просто примените нужный порядок сортировки (самый большой элемент, второй по величине, третий по величине и т. Д.). Это занимает менее 0,2 секунды при n=4.
Результат:
>>> print "\n".join(map(str, gen_all_n_tuples(3)))
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(1, 0, 0)
(0, 1, 1)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
(0, 0, 2)
(0, 2, 0)
(2, 0, 0)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(0, 2, 2)
(2, 0, 2)
(2, 2, 0)
(1, 2, 2)
(2, 1, 2)
(2, 2, 1)
(2, 2, 2)
(0, 0, 3)
(0, 3, 0)
(3, 0, 0)
(0, 1, 3)
(0, 3, 1)
(1, 0, 3)
(1, 3, 0)
(3, 0, 1)
(3, 1, 0)
(1, 1, 3)
(1, 3, 1)
(3, 1, 1)
(0, 2, 3)
(0, 3, 2)
etc...
РЕДАКТИРОВАТЬ: ваши изменения сделали этот заказ недействительным. Оставил здесь для потомков.
Вот алгоритм, который я реализовал на английском языке. По сути, для того, чтобы получить нужный порядок, представьте, что проблема заключается в "генерации всех n-кортежей, по крайней мере, с одним из самых больших элементов". Предполагая, что у нас это есть, все, что нам нужно сделать, это:
- yield `n` zeroes
- for each element greater than zero:
- yield all the n-tuples with at least one of that element
Чтобы сгенерировать все n-кортежи, по крайней мере, с одним из самых больших элементов, я сгенерировал все возможные позиции, в которых мог бы быть элемент - например, для 3-кортежа это будет
no no yes
no yes no
no yes yes
yes no no
yes no yes
yes yes no
yes yes yes
Это просто декартово произведение n (да, нет) выбор. Для каждой возможной позиции мы заполняем все возможные nos. Что может пойти в nos? Любой элемент, который меньше, чем самый большой элемент. Таким образом, вы берете декартово произведение всех элементов, меньших, чем самый большой (включая ноль), x раз, где x это число nos, и заполните эти пробелы тоже. Так что если у вас 3 и позиция no no yes тогда вы делаете:
0 0 3
0 1 3
0 2 3
1 0 3
1 1 3
1 2 3
2 0 3
2 1 3
2 2 3
Вот реализация этого алгоритма на python:
import itertools
alphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
def enumerate_n_tuples(n):
#the zero case:
yield [alphabet[0],]*n
for i in xrange(1, len(alphabet)):
#alphabet[i] is the largest element
#it must be present in the result
largest_el = alphabet[i]
#fill in the largest element in all possible combinations
for largest_el_map in itertools.product(*([(False,True)]*n)):
#other spots are filled freely up to (not including) largest
num_others = sum(1 for largest in largest_el_map
if not largest)
if num_others == n: continue #need at least one largest el
for others in itertools.product(*([alphabet[:i]]*num_others)):
#init the result to zeroes
res = [alphabet[0]]*n
#fill in the largest elements, putting the other
#elements in between
others_i = 0
for j,largest in enumerate(largest_el_map):
if largest:
res[j] = largest_el
else:
res[j] = others[others_i]
others_i += 1
yield res
Пример:
>>> for threetup in enumerate_n_tuples(3):
print threetup
if threetup[-1]==3: break
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
[0, 0, 2]
[0, 1, 2]
[1, 0, 2]
[1, 1, 2]
[0, 2, 0]
[0, 2, 1]
[1, 2, 0]
[1, 2, 1]
[0, 2, 2]
[1, 2, 2]
[2, 0, 0]
[2, 0, 1]
[2, 1, 0]
[2, 1, 1]
[2, 0, 2]
[2, 1, 2]
[2, 2, 0]
[2, 2, 1]
[2, 2, 2]
[0, 0, 3]
Для справки: ответ порта veredesmarald с реализацией Claudiu на C#. Массивы Python, конечно, более кратки.
public IEnumerable<List<int>> Enumerate (int n, int k)
{
if (k == 0) {
yield return new List<int> ();
yield break;
}
yield return Enumerable.Repeat (0, k).ToList ();
for (int i = 1; i <= n; i++) {
foreach (var x in Enumerate (i, k - 1)) {
for (int j = 0; j < k; j++) {
var res = x.Take (j).Concat (new int[] { i }).Concat (x.Skip (j));
yield return res.ToList ();
if (j != k - 1 && x[j] == i) {
break;
}
}
}
}
}
public IEnumerable<List<int>> Enumerate (int k)
{
return Enumerate (int.MaxValue, k);
}
// Test:
foreach (var tuple in Enumerate (3).Take (100)) {
Console.Write (string.Concat (tuple.Select (x => x.ToString ())) + " ");
if (tuple.All (x => x == tuple[0])) {
Console.WriteLine ();
}
}
This algorithm generates the next element that satisfies your constraints.
generateNext(int a[1:m]) {
Let n be the largest number in a.
IF a[i] == n for all i: { // e.g. If a = 111
set a[1] = n+1 and a[j] = 0 for all j in 2 to m.
return
}
ELSE {
Let p be the last position where n appears.
IF a[i] == n for all i to the left of p { // trivially true when p is 1.
set a[i] = 0 for all i to the left of p.
IF a[i] == n-1 for all i to the right of p { // trivially true when p is m.
set a[i] = 0 for all i to the right of p.
set a[p-1] = n
}
ELSE {
generateNext(a[p+1:m])
seta[i] = 0 for all i to the left of p
}
}
ELSE
generateNext(a[1:p-1])
}
}
При вызове с 002 последовательность чисел, которую возвращает алгоритм, должна быть: 002 012 102 112 022 122 202 212 222 020 120 220 021 121 221 200 201 210 211