繰り返し

Question

考えると二組、例えば：

{A B C}, {1 2 3 4 5 6} 

を最小限に抑えながら、デカルト積を列挙私は同じ要素の間にできるだけ多くのスペースを置くために、デカルト積を生成したいです。たとえば、[A1, A2, A3, A4, A5, A6, B1…]は、すべてのAが互いに隣接しているため、正しくありません。

[A1, B2, C3, A4, B5, C6, A2, B3, C4, A5, B6, C1, A3…] 

を視覚的に表現する：

| | A | B | C | A | B | C | A | B | C | A | B | C | A | B | C | A | B | C | 
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| 
| 1 | 1 | | | | | | | | | | | | | | | | | | 
| 2 | | 2 | | | | | | | | | | | | | | | | | 
| 3 | | | 3 | | | | | | | | | | | | | | | | 
| 4 | | | | 4 | | | | | | | | | | | | | | | 
| 5 | | | | | 5 | | | | | | | | | | | | | | 
| 6 | | | | | | 6 | | | | | | | | | | | | | 
| 1 | | | | | | | | | | | | | | | | | | | 
| 2 | | | | | | | 7 | | | | | | | | | | | | 
| 3 | | | | | | | | 8 | | | | | | | | | | | 
| 4 | | | | | | | | | 9 | | | | | | | | | | 
| 5 | | | | | | | | | | 10| | | | | | | | | 
| 6 | | | | | | | | | | | 11| | | | | | | | 
| 1 | | | | | | | | | | | | 12| | | | | | | 
| 2 | | | | | | | | | | | | | | | | | | | 
| 3 | | | | | | | | | | | | | 13| | | | | | 
| 4 | | | | | | | | | | | | | | 14| | | | | 
| 5 | | | | | | | | | | | | | | | 15| | | | 
| 6 | | | | | | | | | | | | | | | | 16| | | 
| 1 | | | | | | | | | | | | | | | | | 17| | 
| 2 | | | | | | | | | | | | | | | | | | 18| 

または、同等しかし、行/列を繰り返すことなく受け入れ可能な解決策は、それが1によって相殺ラップするたびに、例えば「対角線の下」に行くことになります：

他の解決策もありますが、それは私が最も簡単に考えるものです。しかし、私は壁に向かって頭を叩いて、それを一般的に表現する方法を見つけようとしています.2つのセットの基数がお互いの倍数であるのは便利なことですが、アルゴリズムでは、サイズ5と7、またはサイズ12と69（実際の例です）のようになります。

これについて確立されたアルゴリズムはありますか？私は、有理数が自然数の集合にどのように写像されているかを考えて（計算可能であることを証明するために）注意をそらし続けますが、この場合はℕ×pathを通る経路は機能しません。

とてもアプリケーションがRubyで書かれているが起こるが、私は、言語を気にしないでください。擬似コード、Ruby、Python、Java、Clojure、Javascript、CL、英語の段落 - あなたの好みを選んでください。 Pythonで

---

概念実証ソリューションは、（すぐにルビーに移植し、レールとフックアップする）：

import sys 

letters = sys.argv[1] 
MAX_NUM = 6 

letter_pos = 0 
for i in xrange(MAX_NUM): 
    for j in xrange(len(letters)): 
     num = ((i + j) % MAX_NUM) + 1 
     symbol = letters[letter_pos % len(letters)] 
     print "[%s %s]"%(symbol, num) 
     letter_pos += 1 

Answer 1

String letters = "ABC"; 
int MAX_NUM = 6; 

int letterPos = 0; 
for (int i=0; i < MAX_NUM; ++i) { 
    for (int j=0; j < MAX_NUM; ++j) { 
     int num = ((i + j) % MAX_NUM) + 1; 
     char symbol = letters.charAt(letterPos % letters.length); 
     String output = symbol + "" + num; 
     ++letterPos; 
    } 
} 

Answer 2

ご集合XとYは、サイズmとnはしている場合、およびXiがあなたの対角線李を得ることができ、その後

Xi = i mod n; 
Yi = (i mod n + i div n) mod m; 

あなたの直積でi番目のペアにありますXの要素のインデックス（およびYについても同様）であり、あなたの行列を次のように塗りつぶしてより広がります。

for (int i = 0; i < m*n; i++) { 
    int xi = i % n; 
    int yi = i % m; 
    while (matrix[yi][xi] != 0) { 
    yi = (yi+1) % m; 
    } 
    matrix[yi][xi] = i+1; 
} 

Answer 3

何かフラクタル/再帰的なものを使うのはどうですか？この実装では、四角形の範囲を4つの象限に分割し、各象限からポイントを生成します。これは、シーケンス内の隣接点が少なくとも四分円で異なることを意味します。

#python3 

import sys 
import itertools 

def interleave(*iters): 
    for elements in itertools.zip_longest(*iters): 
    for element in elements: 
     if element != None: 
     yield element 

def scramblerange(begin, end): 
    width = end - begin 

    if width == 1: 
    yield begin 

    else: 
    first = scramblerange(begin, int(begin + width/2)) 
    second = scramblerange(int(begin + width/2), end) 
    yield from interleave(first, second) 

def scramblerectrange(top=0, left=0, bottom=1, right=1, width=None, height=None): 
    if width != None and height != None: 
    yield from scramblerectrange(bottom=height, right=width) 
    raise StopIteration 

    if right - left == 1: 
    if bottom - top == 1: 
     yield (left, top) 

    else: 
     for y in scramblerange(top, bottom): 
     yield (left, y) 

    else: 
    if bottom - top == 1: 
     for x in scramblerange(left, right): 
     yield (x, top) 

    else: 
     halfx = int(left + (right - left)/2) 
     halfy = int(top + (bottom - top)/2) 

     quadrants = [ 
     scramblerectrange(top=top, left=left, bottom=halfy, right=halfx), 
     reversed(list(scramblerectrange(top=top, left=halfx, bottom=halfy, right=right))), 
     scramblerectrange(top=halfy, left=left, bottom=bottom, right=halfx), 
     reversed(list(scramblerectrange(top=halfy, left=halfx, bottom=bottom, right=right))) 
     ] 

     yield from interleave(*quadrants) 

if __name__ == '__main__': 
    letters = 'abcdefghijklmnopqrstuvwxyz' 
    output = [] 

    indices = dict() 
    for i, pt in enumerate(scramblerectrange(width=11, height=5)): 
    indices[pt] = i 
    x, y = pt 
    output.append(letters[x] + str(y)) 

    table = [[indices[x,y] for x in range(11)] for y in range(5)] 

    print(', '.join(output)) 
    print() 
    pad = lambda i: ' ' * (2 - len(str(i))) + str(i) 
    header = ' |' + ' '.join(map(pad, letters[:11])) 
    print(header) 
    print('-' * len(header)) 
    for y, row in enumerate(table): 
    print(pad(y)+'|', ' '.join(map(pad, row))) 

出力：

a0, i1, a2, i3, e0, h1, e2, g4, a1, i0, a3, k3, e1, 
h0, d4, g3, b0, j1, b2, i4, d0, g1, d2, h4, b1, j0, 
b3, k4, d1, g0, d3, f4, c0, k1, c2, i2, c1, f1, a4, 
h2, k0, e4, j3, f0, b4, h3, c4, j2, e3, g2, c3, j4, 
f3, k2, f2 

    | a b c d e f g h i j k 
----------------------------------- 
0| 0 16 32 20 4 43 29 13 9 25 40 
1| 8 24 36 28 12 37 21 5 1 17 33 
2| 2 18 34 22 6 54 49 39 35 47 53 
3| 10 26 50 30 48 52 15 45 3 42 11 
4| 38 44 46 14 41 31 7 23 19 51 27