配列の圧縮について

[徹朗]

はじめまして, 配列の圧縮方法について質問させていただきます.

例えば,
0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0
のような正方行列の配列について, 0のみの行(列)についてその行(列)を削除して
1 4
2 3
0 5
のような新たな配列を作成したいのですが, うまく行きません.

2*2程度の行列であれば2次元配列を1次元配列に落として以下の様なプログラムを作成して実装できたのですが,
10*10以上の行列で行うと, この方法では不格好になってしまいます.

コード:

#define N 2

int main(){
int i, j;
int a[SIZE] = {0,1};
int b[SIZE] = {0,2};

  for(i = 0; i < SIZE; i++){
    if(a[i] == 0 && b[i] == 0){
      for(j = i+1; j < SIZE; j++){
	a[j-1] = a[j];
	b[j-1] = b[j];
      }
      i--;
    }
  }
}

よい方法をご存知の方, 回答宜しくお願いします.

[cattail]

0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0

を圧縮する方法として
例えば、横方向に、

00104
00203
\05
\045
\05

になるようにすれば
圧縮率は低いですが損失が0でカンタンです。
また、縦に圧縮するともう少し良くなります。
この場合、ですけども。

全然ダメですね、ごめんなさい。

[徹朗]

返信有難うございます.

たしかにその方法でも圧縮が出来ますね, ただ, 行(列)がすべて0となった時のみに削除を行いたいです.
ちなみにいい忘れていましたが, 元のデータは2次元配列に格納されています.
引き続き, 回答をよろしくお願いします...

[みけCAT]

よい方法かはわかりませんが、新たな配列を作成しやすいJavaで素直に書いてみました。
エラーチェックは省略しました。

コード:

public class Main {
	public static int[][] assyuku(int[][] array) {
		int[] rowData = new int[array.length];
		int[] colData = new int[array[0].length];
		int rowDataSize = 0;
		int colDataSize = 0;
		// 行について調査する
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				if (array[i][j] != 0) {
					// 0以外のデータがあったら、その行を拾う
					rowData[rowDataSize++] = i;
					break;
				}
			}
		}
		// 列について調査する
		for (int j = 0; j < array[0].length; j++) {
			for (int i = 0; i < array.length; i++) {
				if (array[i][j] != 0) {
					// 0以外のデータがあったら、その列を拾う
					colData[colDataSize++] = j;
					break;
				}
			}
		}
		// 結果を作成する
		int[][] result = new int[rowDataSize][colDataSize];
		for (int i = 0; i < rowDataSize; i++) {
			for (int j = 0; j < colDataSize; j++) {
				result[i][j] = array[rowData[i]][colData[j]];
			}
		}
		return result;
	}

	public static void printArray(int[][] array) {
		for (int i = 0; i < array.length; i++) {
			if (array[i].length > 0) System.out.print(array[i][0]);
			for (int j = 1; j < array[i].length; j++) {
				System.out.print(" " + array[i][j]);
			}
			System.out.println();
		}
	}

	public static void doTest(int[][] data, String name) {
		System.out.println(name + " input");
		printArray(data);
		int[][] res = assyuku(data);
		System.out.println(name + " output");
		printArray(res);
	}

	public static void main(String[] args) {
		int[][] case1 = {
			{0, 1},
			{0, 2}
		};
		int[][] case2 = {
			{0, 0, 1, 0, 4},
			{0, 0, 2, 0, 3},
			{0, 0, 0, 0, 0},
			{0, 0, 0, 0, 5},
			{0, 0, 0, 0, 0}
		};
		doTest(case1, "case 1");
		doTest(case2, "case 2");
	}
}

実行結果

コード:

case 1 input
0 1
0 2
case 1 output
1
2
case 2 input
0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0
case 2 output
1 4
2 3
0 5

[Rittai_3D]

言語が指定されていないので、C++で大雑把に書いてみました。
エラーチェックはしていないです。

► スポイラーを表示

コード:

#include <iostream>
#include <vector>


using namespace std;


// 二次元配列のつもり
using arr2 = vector< vector< int > >;

// 出力
inline void printArr2( const arr2& a )
{
	for( auto& it1 : a ) {
		for( auto& it2 : it1 ) {
			cout << it2;
		}
		cout << endl;
	}
}

// 圧縮処理 
inline arr2 Asshuku( const arr2& a )
{
	arr2 ret = {};

	for( auto& it1 : a ) {
		auto tmp = vector< int > {};

		for( auto& it2 : it1 ) {
			if( it2 != 0 ) {
				tmp.push_back( it2 );
			}
		}

		// 空じゃなければ追加
		if( !tmp.empty() ) {
			ret.push_back( tmp );
		}
	}

	return ret;
}

int main( void )
{
	// 圧縮前
	static const arr2 src =
	{
		{ 0, 0, 1, 0, 4, },
		{ 0, 0, 2, 0, 3, },
		{ 0, 0, 0, 0, 0, },
		{ 0, 0, 0, 0, 5, },
		{ 0, 0, 0, 0, 0, },
	};

	// 圧縮後
	auto dst = Asshuku( src );

	// 圧縮前表示
	cout << "before" << '\n' << "--------------------" << endl;
	printArr2( src );

	// 圧縮後表示
	cout << '\n' << "after" << '\n' << "--------------------" << endl;
	printArr2( dst );
}

実行結果です→http://melpon.org/wandbox/permlink/VCJXV3ASNYAUDuwc

► スポイラーを表示

コード:

Start
before
--------------------
00104
00203
00000
00005
00000

after
--------------------
14
23
5

0
Finish

#追記
出力結果が空白が無くて見にくかったのでちょっと修正しました。
http://melpon.org/wandbox/permlink/WJ9eD7EUpZiOha3N
#さらに追記
何度も何度もすいません。
要素が一つの時に0を追加するのを忘れていました。
http://melpon.org/wandbox/permlink/GaOQruZfwaK2p72q

[徹朗]

[quote="みけCAT" id=3,16804,131607]よい方法かはわかりませんが、新たな配列を作成しやすいJavaで素直に書いてみました。

返信有難うございます.
Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.
ありがとうございました！

[徹朗]

[quote="Rittai_3D" id=3,16804,131608]言語が指定されていないので、C++で大雑把に書いてみました。

返信有難うございます, 無事解決出来ました!
ありがとうございました!

[かずま]

Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.

他の人の参考になるように、その C のプログラムを提示してください。

私は、次のように書いてみました。

コード:

#include <stdio.h>

void compress(void *p, int sz, int *pm, int *pn)
{
    int *a = p, i, j, m, n;
    for (m = i = 0; i < sz; i++)
        for (j = 0; j < sz; j++) {
            if (a[i*sz + j]) {
                if (m < i)
                    for (j = 0; j < sz; j++) a[m*sz + j] = a[i*sz + j];
                m++;
                break;
            }
        }
    for (n = j = 0; j < sz; j++)
        for (i = 0; i < m; i++) {
            if (a[i*sz + j]) {
                if (n < j)
                    for (i = 0; i < m; i++) a[i*sz + n] = a[i*sz + j];
                n++;
                break;
            }
        }
    *pm = m, *pn = n;
}

void print(void *p, int sz, int m, int n)
{
    int *a = p, i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            printf(" %4d", a[i*sz + j]);
        putchar('\n');
    }
}

int a[2][2] = {
    { 0, 1 },
    { 0, 2 },
};
int b[5][5] = {
    { 0, 0, 1, 0, 4 },
    { 0, 0, 2, 0, 3 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5 },
    { 0, 0, 0, 0, 0 },
};

int main(void)
{
    int m, n;

    puts("A input"), print(a, 2, 2, 2);
    compress(a, 2, &m, &n);
    puts("A output"), print(a, 2, m, n);

    puts("B input"), print(b, 5, 5, 5);
    compress(b, 5, &m, &n);
    puts("B output"), print(b, 5, m, n);

    return 0;
}

[徹朗]

Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.

他の人の参考になるように、その C のプログラムを提示してください。

返信有難うございます.
失礼しました, 非常に見づらいですがこのように書きました.

コード:

#include <stdio.h>

#define N 5

int main(){

  int array[N][N] = {
    {0, 0, 1, 0, 4},
    {0, 0, 2, 0, 3},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 5},
    {0, 0, 0, 0, 0}
  };

  int a1[N][N] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
  };

  int a2[N][N] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
  };

  int i, j, k;
  int count = 0;
  int count2 = 0;

  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(array[i][j] != 0){
        for(k = j; k < N; k++){
          a1[count][k] = array[i][k];
        }
        count++;
        break;
      }
    }
  }

  for(j = 0; j < N; j++){
    for(i = 0; i < N; i++){
      if(array[i][j] != 0){
        for(k = i; k < N; k++){
          a2[k][count2] = a1[k][j];
        }
        count2++;
        break;
      }
    }
  }

  /* 表示 */
  int a3[N-count2][N-count];

  for(i = 0; i < N-count2; i++){
    for(j = 0; j < N-count; j++){
      a3[i][j] = a2[i][j];
      printf("%d ", a3[i][j]);
    }
    printf("\n");
  }

  return 0;
}

[かずま]

失礼しました, 非常に見づらいですがこのように書きました.

{0, 0, 1, 0, 4}, を
{6, 0, 1, 0, 4}, に変えてみてください。
望みどおりの結果にはならないでしょう。

また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。

[みけCAT]

また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。

これは違うのではないでしょうか？
gccの-pedantic-errorssオプションを付けてもC99としてコンパイルが通りました。
また、N1256の117～118ページ(PDF上では129～130ページ)にも、
変数による配列(variable length array type)のサイズの宣言の例が載っています。

[徹朗]

失礼しました, 非常に見づらいですがこのように書きました.

{0, 0, 1, 0, 4}, を
{6, 0, 1, 0, 4}, に変えてみてください。
望みどおりの結果にはならないでしょう。

失礼しました, 配列を表示する部分が正しくありませんでした.
ご指摘ありがとうございます.

コード:

  /* 表示 */
  int a3[count][count2];

  for(i = 0; i < count; i++){
    for(j = 0; j < count2; j++){
      a3[i][j] = a2[i][j];
      printf("%d ", a3[i][j]);
    }
    printf("\n");
  }

[かずま]

また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。

これは違うのではないでしょうか？
gccの-pedantic-errorssオプションを付けてもC99としてコンパイルが通りました。
また、N1256の117～118ページ(PDF上では129～130ページ)にも、
変数による配列(variable length array type)のサイズの宣言の例が載っています。

おっしゃる通りです。「VC++ ではコンパイルできません」と言いたかったのを、
他にも Borland C Compile なんかもそうだろうから違った表現にしようとして、
あんなふうに書いてしました。

C99 からは可変長配列が使えるので、私のプログラムも次のように書けます。

コード:

#include <stdio.h>

void compress(int sz, int a[sz][sz], int *pm, int *pn)
{
    int i, j, m, n;
    for (m = i = 0; i < sz; i++)
        for (j = 0; j < sz; j++)
            if (a[i][j]) {
                if (m < i)
                    for (j = 0; j < sz; j++) a[m][j] = a[i][j];
                m++;
                break;
            }
    for (n = j = 0; j < sz; j++)
        for (i = 0; i < m; i++)
            if (a[i][j]) {
                if (n < j)
                    for (i = 0; i < m; i++) a[i][n] = a[i][j];
                n++;
                break;
            }
    *pm = m, *pn = n;
}

void print(int sz, int a[sz][sz], int m, int n)
{
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            printf(" %4d", a[i][j]);
        putchar('\n');
    }
}

int a[2][2] = {
    { 0, 1 },
    { 0, 2 },
};
int b[5][5] = {
    { 0, 0, 1, 0, 4 },
    { 0, 0, 2, 0, 3 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5 },
    { 0, 0, 0, 0, 0 },
};

int main(void)
{
    int m, n;

    puts("A input"), print(2, a, 2, 2);
    compress(2, a, &m, &n);
    puts("A output"), print(2, a, m, n);

    puts("B input"), print(5, b, 5, 5);
    compress(5, b, &m, &n);
    puts("B output"), print(5, b, m, n);

    return 0;
}

使用メモリサイズやコピー回数がなるべく少なくなることを意識したプログラムです。