algorithm - nタプルのフラット順列（幅優先）

Question

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 ケースの画像。緑色の線は、タプル内の要素の順序をシャッフルすることによって到達する要素を示します。

編集：注文に関する説明：

1. タプルは主に最大要素 (152 > 444) でソートされます
2. 次に、2 番目に大きい要素 (053 > 252) など (12341 > 12340) で並べ替えられます。
3. 同じ要素を持つタプル間の順序は任意です (123 = 321)

Answer 1

からまでの数字を使用して、エントリごとの数字で必要なシーケンスseq(n, k)を生成します。k0n

stepiを、最大桁数が であるすべてのタプルを生成するフェーズとしますi。

各ステップで、単純に までのすべての数値(つまり、桁まで) のi+1-ary 表現を生成します。各-ary 表現に対して、 -ary 表現の各位置に数字を挿入することにより、シーケンスの要素を生成します。(i+1) ** (k - 1) - 1k-1i+1ii+1

重複を避けるために、i既にi+1-ary 表現に遭遇した場合に早期に中断します。

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

また、Claudu のおかげで、ジェネレーターとタプルのバージョンがあります。

# 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

Answer 2

わかりました、あなた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

簡単な説明: すべての可能なタプルを生成し、必要な並べ替え順序 (最大の要素、2 番目に大きい、3 番目に大きいなど) を適用するだけです。n=4 の場合、これにかかる時間は 0.2 秒未満です。

結果：

>>> 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...

Answer 3

編集: あなたの編集により、この順序は無効になりました。後世のためにここに残しました。

これが私が英語で実装したアルゴリズムです。基本的に、必要な順序を取得するには、問題を「指定された最大要素の少なくとも 1 つを含むすべての n タプルを生成する」と考えてください。それがあると仮定すると、私たちがしなければならないことは次のとおりです。

- yield `n` zeroes
- for each element greater than zero:
  - yield all the n-tuples with at least one of that element

与えられた最大の要素の少なくとも 1 つを持つすべての n タプルを生成するために、要素が存在する可能性のあるすべての可能な位置を生成しました。たとえば、3 タプルの場合は次のようになります。

no  no  yes
no  yes no
no  yes yes
yes no  no
yes no  yes
yes yes no 
yes yes yes

それは、n(はい、いいえ) の選択肢のデカルト積です。可能な位置ごとに、可能なすべてnoの を埋めます。何が入ることができnoますか？最大の要素より小さい任意の要素。xそのためには、最大 (0 を含む)よりも小さいすべての要素のデカルト積 (xは s の数) を取り、noそれらの空白も埋めます。したがって、 maximum_el が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]

Answer 4

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 で呼び出された場合、アルゴリズムが返す一連の数字は次のようになります。

Answer 5

参考までに、C# への Claudiu の実装を使用した veredesmarald の回答の移植。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 ();
    }
}