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

Question

正の整数nが与えられたとき、次のようなn * nの二次元配列を生成する関数を作成してください。

1. 一番左上の値は 1 です。
2. 左下方向に行くに従って値が１ずつ増えていきます。
3. これ以上左下方向に行けなくなったら、右上の次の位置に戻ります。

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

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

を生成します。

プログラム言語は何でも構いません。命令型でも関数型でも大丈夫です。

---

解決後追記：

より良い回答を頂いた後に何なんですが、念のため昨日質問をする前に私が書いたコードを載せておきます。

	public static int[][] makeArray(int n) {
		int[][] array = new int[n][n];

		int num = 1;
		int istart = 0, jstart = 0;
		int i = 0, j = 0;

		while (true) {
			array[i][j] = num;
			num++;

			// リセットの場合
			if (i == jstart && j == istart) {
				// 終了の場合
				if (i == n - 1 && j == n - 1)
					break;

				if (istart != n - 1) {
					istart++;
				} else {
					jstart++;
				}
				i = istart;
				j = jstart;
				continue;
			}
			// 続ける場合
			i--;
			j++;
		}
		return array;
	}

Answer 1

function hoge ( n ) {
	var ary = [];
	var i;

	for ( i = 0; i < n; i ++ ) {
		ary[ i ] = [];
	}
	
	fuga( ary, 0, 0, 1, n );
	moga( ary, n - 1, n - 1, n * n, n );
	
	function fuga( ary, i, j, x, n ) {
		if ( j == n ) return;
		
		ary[ i ][ j ] = x;

		if ( j == 0 ) {
			fuga( ary, j, i + 1, x + 1, n );
		} else {
			fuga( ary, i + 1, j - 1, x + 1, n );
		}
	}

	function moga( ary, i, j, x, n ) {
		if ( i == n - 1 && j == 0 ) return;
		
		ary[ i ][ j ] = x;

		if ( j == n - 1 ) {
			moga( ary, j, i - 1, x - 1, n )
		} else {
			moga( ary, i - 1, j + 1, x - 1, n );
		}
	}

	return ary;
}

console.log( hoge( 4 ) );

あまりきれいなプログラムじゃありませんが

function hoge ( n ) {
	var ary = [];
	var i;

	for ( i = 0; i < n; i ++ ) {
		ary[ i ] = [];
	}
	
	moga( ary, 0, 0, 1, 1, n );

	function fuga( ary, i, j, x, y, n ) {
		if ( y < 0 || j < 0 ) return;
		
		if ( i < n && j < n ) {
			ary[ i ][ j ] = x;
		}
		if ( i == 0 ) {
			fuga( ary, i + 1, j - 1, x + 1, 0, n );
			x += y;
			if ( j < n - 2 ) {
				y++;
			} else if ( j > n - 2 ) {
				y--;
			}
			fuga( ary, i, j + 1, x, y, n );
		} else {
			fuga( ary, i + 1, j - 1, x + 1, y, n );
		}
	}

	return ary;
}

console.log( hoge( 4 ) );

function hoge( n ) {
	var ary = [];
	var i, j, k, x = 1;
	
	for ( i = 0; i < n; i ++ ) ary[ i ] = [];

	for ( k = 0; k <= ( n - 1 ) * 2; k ++ )
		for ( i = 0, j = k; j >= 0; i ++, j -- )
			if ( i < n && j < n )
				ary[ i ][ j ] = x ++;

	return ary;
}
console.log( hoge( 4 ) );

最短で４行、これ以上無理

Comments

[Chironian]

最短4行の案、スマートで良いですね！
正方形をカバーする大きな三角形を描いて、正方形内のみ描画するって感じですね。

[yuux01]

９つの点を通る一筆書きを思い出したんです。
ただ、はみ出す分、無駄な処理がありますが。

[yuux01]

for( i = 0; i < n; i++ )
for( j = 0; j <= i; j++ ) {
ary[ j ][ i - j ] = x ++;
ary[ n - j - 1 ][ n - i + j - 1 ] = n * n + 1 - ary[ j ][ i - j ];
}

catsforepaw さんのをお借りして、4.5行プログラムｗ
若干無駄が少なくなってます。

数列の和を参考にしてみました。

[t-miyazaki]

回答ありがとうございます。ベストアンサーの方のところに総括してコメントを
入れさせていただきました。

最後の４行のプログラム、こちらもかなりまとまっていて良いですね。

Answer 2

こんなところでしょうか。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

std::vector<std::vector<int>> generate(int n)
{
	std::vector<std::vector<int>> data(n);
	std::fill(data.begin(), data.end(), std::vector<int>(n));

	// ◤の部分
	int a = 1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j <= i; j++)
		{
			data[j][i - j] = a++;
		}
	}
	// ◢の部分
	a = n * n;
	for(int i = 0; i < n - 1; i++)
	{
		for(int j = 0; j <= i; j++)
		{
			data[(n - 1) - j][(n - 1) - (i - j)] = a--;
		}
	}
	return data;
}

int main()
{
	for(;;)
	{
		int n;
		std::cout << "n (0=exit) ? ";
		std::cin >> n;
		if(n == 0)
			break;

		auto data = generate(n);
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				printf(" %4d", data[i][j]);
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}
	return 0;
}

平行四辺形にすることに気づいたらコードが単純化できました。

Comments

[t-miyazaki]

回答ありがとうございます。ベストアンサーの方のところに総括してコメントを
入れさせていただきました。

Answer 3

yuux01 さんの解を ruby でかいてみました。

斜め線でスキャンをしていき、正方形領域にひっかかったときだけ
配列に値を設定していきます。
(x < n && y < n が正方形の内部か? の判定になります。
この判定部分を変更すると、三角形や円の形で切り取ることができるようになります。)

def gen_square(n)
  ary = Array.new(n).map! { Array.new(n, 0) }
  seq = 1
  (0..n * 2 - 1).each do |scan_line|
    (0..scan_line).each do |y|
      x = scan_line - y
      if x < n && y < n
        ary[y][x] = seq
        seq += 1
      end
    end
  end
  ary
end

def show_square(ary)
  return if ary.size == 0
  keta = Math.log10(ary.size * ary.size).floor + 2
  fmt = "%#{keta}d"
  ary.each do |line|
    s = ''
    line.each do |item|
      s += format(fmt, item)
    end
    puts s
  end
end

[0, 1, 2, 3, 4, 10].each do |d|
  ary = gen_square(d)
  show_square(ary)
  puts
end

実行例

 1

 1 2
 3 4

 1 2 4
 3 5 7
 6 8 9

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

   1   2   4   7  11  16  22  29  37  46
   3   5   8  12  17  23  30  38  47  56
   6   9  13  18  24  31  39  48  57  65
  10  14  19  25  32  40  49  58  66  73
  15  20  26  33  41  50  59  67  74  80
  21  27  34  42  51  60  68  75  81  86
  28  35  43  52  61  69  76  82  87  91
  36  44  53  62  70  77  83  88  92  95
  45  54  63  71  78  84  89  93  96  98
  55  64  72  79  85  90  94  97  99 100

Answer 4

ary[y][x] の値を求める関数を func(x, y, n) としてくくりだして、
2 次元配列に値を設定するようにしました。

ary[0][x] (四角の上辺の値)は (x * x + x) / 2 + 1 で計算できること、
ary[n-1][n-1-x] (四角の下辺の値)は n * n - (y * y + y) / 2 で計算できること、
を使って、 それ以外の ary[y][x] の値を計算しています。

四角の上辺の値 1, 2, 4, 7, 11, ... の数列は
隣同士の差が 1, 2, 3, 4, ... となっています。

def sub(x)
  (x * x + x) / 2
end

def func(x, y, n)
  if x + y < n
    sub(x + y) + 1 + y
  else
    n * n - sub(2 * n - 1 - x - y) + n - x
  end
end

def gen_square(n)
  ary = Array.new(n).map! { Array.new(n, 0) }
  (0..n - 1).each do |y|
    (0..n - 1).each do |x|
      ary[y][x] = func(x, y, n)
    end
  end
  ary
end

def show_square(ary)
  return if ary.size == 0
  keta = Math.log10(ary.size * ary.size).floor + 2
  fmt = "%#{keta}d"
  ary.each do |line|
    s = ''
    line.each do |item|
      s += format(fmt, item)
    end
    puts s
  end
end

[0, 1, 2, 3, 10].each do |d|
  ary = gen_square(d)
  show_square(ary)
  puts
end

実行結果

1

 1 2
 3 4

 1 2 4
 3 5 7
 6 8 9

   1   2   4   7  11  16  22  29  37  46
   3   5   8  12  17  23  30  38  47  56
   6   9  13  18  24  31  39  48  57  65
  10  14  19  25  32  40  49  58  66  73
  15  20  26  33  41  50  59  67  74  80
  21  27  34  42  51  60  68  75  81  86
  28  35  43  52  61  69  76  82  87  91
  36  44  53  62  70  77  83  88  92  95
  45  54  63  71  78  84  89  93  96  98
  55  64  72  79  85  90  94  97  99 100

追記：
v -> Ux,y) を求める方法は次のようになります。

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 gen_square(n)
  ary = Array.new(n).map! { Array.new(n, 0) }
  (1..n * n).each do |v|
    x, y = pos(v, n)
    ary[y][x] = v
  end
  ary
end

Comments

[katoy]

上では (x, y) -> v (配列の位置から埋めるべきを求める) で配列を埋めていきましたが、
逆に v -> (x, y) (値 v が現れる 配列の位置を求める) を使って配列を埋めていくという解法も考えられます。

[t-miyazaki]

ご回答いただき、どうもありがとうございました。

もともとは、このような正方行列の行列式を計算したかったのですが、
任意のnにおける正方行列の生成を自分ではエレガントに書けませんでしたので
質問させていただいた次第です。

規則的な配列でもスマートに書こうと思うとなかなか難しいこと、
人によっても実装の仕方がけっこう変わってくることが面白く思いました。

理想的には、位置(x,y)における要素の値を算出できる一般式を用いて書くと
すっきり書けると思います。
今回は、そのような回答を与えてくださったkatoyさんの回答をベストアンサーとさせて
いただきたいと思います。
重ね重ね、ありがとうございました。

[katoy]

この質問については、結局 4つの方針の解を書いてしまいました。
1. (x, y) -> v　の関数を作って、配列を埋める。
2. v -> (x, y) の関数を作って、配列を埋める。
3. 配列をたどる手順をそのままコーディングする
4. Scan_line で該当図形とのマスクをとる。
さらに他の発想による解もあると思っています。

Answer 5

2重ループ１つでなんとかなりました。

yは各行の先頭の値です。
横へ移動した時の増分をコントロールして各要素に入れる数値xを生成しています。
左上△エリアと右下△エリアで増分の計算式が変わっています。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <climits>

typedef std::vector<std::vector<int> > Array2D;

Array2D createArray(size_t n)
{
    Array2D wArray2D(n, std::vector<int>(n));

    int y=1;
    for (int j=0; j < n; ++j) {
        int x=y;
        for (int i=0; i < n; ++i) {
            wArray2D[i][j]=x;
            if (i < (n-j-1))
                x += (j+i+1);
            else
                x += (n-j-1 + n-i-1);
        }
        y += (j+2);
    }

    return wArray2D;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
return 1;

    size_t  n=strtoul(argv[1], 0, 10);
    if ((n == 0) || (n == ULONG_MAX))
return 1;

    Array2D wArray2D = createArray(n);
    for (int j=0; j < n; ++j) {
        for (int i=0; i < n; ++i) {
            std::cout << std::setw(4) << wArray2D[i][j];
        }
        std::cout << "\n";
    }

    return 0;
}

2重配列をコピーで返却しているので、本当はstd::move()を使って返却した方がよいです。
std::move()はC++11以上でないと使えないので、ここでは見送りました。。

---

【閑話休題】
しかし、こんなに短いプログラムでも、C++11の恩恵が3箇所もありました。(nullptr, テンプレート・パラメータの閉じ括弧>>, std::move)
C++11って偉大です。

Comments

[t-miyazaki]

回答ありがとうございます。ベストアンサーの方のところに総括してコメントを
入れさせていただきました。

Answer 6

質問文の手順をそのままコードにしてみました。

# See https://teratail.com/questions/20823
def gen_square(n)
  ary = Array.new(n).map! { Array.new(n, 0) }
  seq = 1
  (0..n - 1).each do |x|
    (0..x).each do |i|
      ary[i][x - i] = seq
      seq += 1
    end
  end

  (1..n - 1).each do |y|
    (0..n - 1 - y).each do |i|
      ary[y + i][n - 1 - i] = seq
      seq += 1
    end
  end
  ary
end

def show_square(ary)
  return if ary.size == 0
  keta = Math.log10(ary.size * ary.size).floor + 2
  fmt = "%#{keta}d"
  ary.each do |line|
    s = ''
    line.each do |item|
      s += format(fmt, item)
    end
    puts s
  end
end

[0, 1, 2, 3, 10].each do |d|
  ary = gen_square(d)
  show_square(ary)
  puts
end

実行例：

$ ruby 1.rb

 1

 1 2
 3 4

 1 2 4
 3 5 7
 6 8 9

   1   2   4   7  11  16  22  29  37  46
   3   5   8  12  17  23  30  38  47  56
   6   9  13  18  24  31  39  48  57  65
  10  14  19  25  32  40  49  58  66  73
  15  20  26  33  41  50  59  67  74  80
  21  27  34  42  51  60  68  75  81  86
  28  35  43  52  61  69  76  82  87  91
  36  44  53  62  70  77  83  88  92  95
  45  54  63  71  78  84  89  93  96  98
  55  64  72  79  85  90  94  97  99 100

ary[i]j] を計算で求めることができれば、単純なコードにできます。
( 九九の表なら ary[y][x] = (y+1) * (x+1) を単純に代入していくだけですむように)
□の左上と右下の三角形にわければ、計算式が書ける気がするんですが...

Answer 7

少しコードが汚い気もするのですが，こんな感じでどうでしょう？
左上から始めて添え字を左下方向に動かしていきます．（x -= 1，y += 1）
x が左端を超える場合やyが下の端を超える場合（x == 0 or y+1 == size）は
正しい位置に移動するように添え字を代入します．
左上半分を埋めている時は，単純にx = y+1，y = 0で十分です．
右下半分に差し掛かった時は，直前のyとxの位置に合わせてyの位置を工夫する必要があります．

#!/usr/bin/python
import numpy as np
size = int(input())
array = np.zeros([size, size])

x = 0
y = 0
for i in range(size*size):
        array[y][x] = i+1
        if x == 0 or y+1 == size:
                tx = x
                x = y+1 if (y+1 < size) else size-1
                y = 0 if (y+1 < size and tx == 0) else (y+1)+(tx+1)-size
        else:
                x -= 1
                y += 1

print array

配列の添え字が0から始まる言語と1から始まる言語とでは書き方が若干変わると思いますが，
1から始まる言語では適宜xとyを変更してください．

Comments

[t-miyazaki]

回答ありがとうございます。ベストアンサーの方のところに総括してコメントを
入れさせていただきました。