数字が斜めに増えていく正方配列の生成（アルゴリズム）

Question

正の整数nが与えられたとき、次のようなn * nの二次元配列を生成するコードを教えていただきたいです。

よろしくお願いします。

一番左上の値は 0 です。

例えば、n = 5が与えられたとき、

 0  1  5  6 14
 2  4  7 13 15
 3  8 12 16 21
 9 11 17 20 22
10 18 19 23 24

となります。

Answer 1

あー、せっかく勉強になるようにコードを書いたのに。。。

def iterchain(n):
    L, F = list(range(n ** 2)), True
    for i in range(1, n):
        yield sorted(L[:i], reverse=F)
        L, F = L[i:], not F
    for i in range(n, 0, -1):
        yield sorted(L[:i], reverse=F)
        L, F = L[i:], not F


def iterrows(n):
    source = list(iterchain(n))
    for i in range(n):
        yield [source[i+j].pop(0) for j in range(n)]


for row in iterrows(5):
    print(*row, sep=' ')

Comments

[LouiS0616]

こんなに簡潔に書けるんですね。びっくりしました。

[gotata]

僕が動かすとSyntaxError: invalid syntax
が出るのですがどういうことでしょうか。
どなたかわかる方いますか？

[YouheiSakurai]

ありがとうございます。でもあくまで実務用途外のコードです。読みやすくはないので。

[gotata]

高度過ぎてわかんないです...

[LouiS0616]

> gotataさん
Python2.7使ってたりしませんか？

[gotata]

2.7です

[gotata]

3じゃないと動きませんか？

[LouiS0616]

2から3に移行する際に、print文がprint関数に置き換えられています。

[gotata]

ではどうすればよいですか？？

[YouheiSakurai]

自分で調べることも勉強ですよ。

[gotata]

そうですね。調べてみます。

[gotata]

from __future__ import print_function
でできました。ありがとうございました。

[gotata]

ちなみにhttps://teratail.com/questions/20823
のやり方だと、どうなるかわかりますか？
考えたんですけどわからなくて...
気になって寝れません。

[YouheiSakurai]

そっちのやり方はよくわかりません。大丈夫です、気になっててもいつかは寝れます。寝るのが先かわかる様になるのが先かは貴方次第です。

Answer 2

面白かったのでつい考えてしまいました。
せっかくなので。

from itertools import cycle

def coord(n, reverse_first):
    reverse_or_not = [lambda x: x, reversed]
    if reverse_first:
        reverse_or_not.reverse()
    flip = cycle(reverse_or_not).__next__
    yield from (i for r in range(1, n + 1) for i in flip()(range(r)))
    yield from (i for r in range(1, n) for i in flip()(range(r, n)))

def matrix(n):
    data = [[0] * n for _i in range(n)]
    for n, (x, y) in enumerate(zip(coord(n, True), coord(n, False))):
        data[x][y] = n
    return data

for row in matrix(5):
    print(' '.join(map('{:3d}'.format, row)))

Answer 3

似た問題が過去にありました。
https://teratail.com/questions/20823

...
例えば、n = 4が与えられたとき、

1 2 4 7
3 5 8 11
6 9 12 14
10 13 15 16

この問題での解法をすこし変更すれば対処できるとおもわれます。

追記： 2017-10-17

v -> (x, y) 数字 v を正方形のどの位置 (x, y) に置くかを求める方法を、この質問用に変形させてみました。

gen_square(n) 関数中に

x, y = [y, x] if (x + y).even? # 数字が進む向きを逆転させる

の行を付け加えるだけです。

コード全体を示します。(正方形の描画方法の部分は、参考ページのものから少し変更しています）
sq.rv

def pos(v, n)
  if v <= (n * n + 1) / 2 # 左上半分の三角形
    pos_0(v, n)
  else                    # 右半分の三角形
    x, y = pos_0(n * n + 1 - v, n)
    [n - 1 - x, n - 1 - y]
  end
end

def pos_0(v, n)
  z  = 1 # 四角の上辺の数列の初期値
  d  = 1 # 四角の上辺の数列の次の項との差分
  tx = 0 # 四角の上辺の位置
  if v <= (n * n + 1) / 2
    while z <= v
      z += d
      d += 1
      tx += 1
    end
    z -= (d - 1)
    x = tx - (v - z) - 1
    y = v - z
    [x, y]
  else
    fail "Bad argument v:#{v}, n:#{n}"
  end
end

def square_to_s(ary)
  keta = ary.size.zero? ? 1 : Math.log10(ary.size * ary.size).floor + 2
  fmt = "%#{keta}d"
  ary.each.map { |row| row.map { |item| format(fmt, item) }.join }.join("\n")
end

def gen_square(n)
  ary = Array.new(n).map! { Array.new(n, 0) }
  (1..n * n).each do |v|
    x, y = pos(v, n)
    x, y = [y, x] if (x + y).even? # 数字が進む向きを逆転させる
    ary[y][x] = v - 1
  end
  ary
end

[0, 1, 2, 3, 4, 5, 6].each do |d|
  puts(square_to_s(gen_square(d)))
  puts
end

実行結果：

Comments

[退会済みユーザー]

それは見つけましたが、よければ教えていただきたいです。

[退会済みユーザー]

そのサイトを見たのですがどこを直せばよいかわかりません

[gotata]

>katoyさん
質問しといて退会とは失礼ですね笑
このサイトを参考にしたんですけど左下から右上に上がるときはどうすればよいですかね

[katoy]

コードをなおしてみたものを回答に追記しました。