iT邦幫忙

1

如何壓縮陣列?

原陣列

a[5][4]={{1,2,3,6},
{4,3,1},
{5,4,1,2},
{3,5},
{3,4}};
要怎麼壓縮各列的矩陣變為
b[3][4]={{1,2,3,6},
{4,3,1,5},
{5,4,1,2}};
我們要將原陣列壓縮
第一行為1236
第二行為431發現無法存到1236裡,
所以431再存一列,而發現它還有一個空位可以放一個元素
第三行為5412但上面任一列都沒有5412可以納入所以再開一列
第四行為35,發現第二行可以存變為4315所以跟第二行合併
第五行為34 ,發現4315有了,所以又跟第二行合併
就是該怎麼比較一列一列的陣列呢?
想很久還是想不太出來..

看更多先前的討論...收起先前的討論...
請教一下
34 可以跟 4315 合
那 431 為什麼沒有和 1234 合呢?
weiclin iT邦高手 4 級 ‧ 2018-11-03 17:34:13 檢舉
老師, 我看不懂題目
回海綿寶寶~~~
第一行是1236~沒有1234 ˊˇˋ
回小魚不好意思我剛剛是打錯了現在改成1236
噢噢噢原來是這樣XDDD
了解~~~~
淺水員 iT邦新手 5 級 ‧ 2018-11-03 18:24:49 檢舉
看起來是集合的概念
4
淺水員
iT邦新手 5 級 ‧ 2018-11-03 21:15:04
最佳解答

如果數字是 0 到 9 ,或是有限的
那麼集合的判斷可以用這個方法
https://chart.googleapis.com/chart?cht=tx&chl=%5C%7B%204%2C3%2C1%2C5%20%5C%7D%20%5CRightarrow%20Set_A%20%3D%2058%20%5Cquad%20%20%5Ccdots%20%5Cquad%202%5E4%2B2%5E3%2B2%5E1%2B2%5E5%20%5C%5C%20%5C%7B%203%2C5%20%5C%7D%20%5CRightarrow%20Set_B%20%3D%2040%20%5Cquad%20%20%5Ccdots%20%20%5Cquad%202%5E3%2B2%5E5
if https://chart.googleapis.com/chart?cht=tx&chl=Set_B%20%5Csubset%20Set_A%20%5CRightarrow%20Set_A%20%7C%20Set_B%20%3D%20Set_A

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdint.h>

#define DATA_LENGTH 5

typedef struct{
    int length; //儲存幾個數字
    int buf[4];
    unsigned mask;
} set;


void setDatas(set* p, int n, ...);
void showSetArray(int n,set **arr);

int main()
{
    set database[DATA_LENGTH];
    set *arr[DATA_LENGTH];
    int i,j,n=DATA_LENGTH,k,count;
    unsigned mask;
    
    //因為最多只有 1024 種組合,可以利用查表加速
    //下面這個陣列可以查 mask 位元不為 0 的數量是否 <= 4
    //即(bit_count[mask/32]&1<<mask%32)若為 true 代表可合併
    uint32_t bit_count[]={
        0x7fffffff,0x177fffff,0x177f7fff,0x01571fff,
        0x177f7fff,0x77d77f7f,0x01d73fff,0x0061ffdf,
        0x77ff7fff,0x77df577f,0x0177ff7f,0x76c7639f,
        0x0117177f,0x76c76bd7,0x76c76bbf,0xb86d0d85,
        0x177f7fff,0x015717ff,0x0117177f,0x004119f7,
        0x0177ffff,0x0061ff1f,0x0061ffdf,0x76c6ca21,
        0xcfd77fff,0xffffffff,0x76c76bbf,0x76c66cad,
        0x004119f7,0x0060ff95,0x00401a4b,0x004019f0
    };
    
    //測試資料
    setDatas(database+0,4,1,2,3,6);
    setDatas(database+1,3,4,3,1);
    setDatas(database+2,4,5,4,1,2);
    setDatas(database+3,2,3,5);
    setDatas(database+4,2,3,4);
    
    //用指標指向每一列,方便操作
    //(刪除、移動時減少記憶體的讀寫量)
    for(i=0;i<DATA_LENGTH;++i)
        arr[i]=database+i;
    
    //顯示測試資料(初始狀態)
    printf("initial:\n");
    showSetArray(n,arr);
    printf("-------------\n\n");
    
    //開始壓縮
    for(i=1;i<n;++i)
    {
        //子集合處理
        k=0;
        for(j=0;j<i;++j)
        {
            //利用位元運算判斷誰是誰的子集合
            mask=arr[i]->mask|arr[j]->mask;
            if(mask==arr[j]->mask)
            {// i 為 j 的子集, 刪除 i
                memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
                --i;
                k=1;
                break;
            }
            if(mask==arr[i]->mask)
            {// j 為 i 的子集, 用 i 取代 j
                arr[j]=arr[i];
                memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
                --i;
                k=1;
                break;
            }
        }
        if(k)
            continue;
        
        //如果不存在子集合關係,嘗試合併集合
        for(j=0;j<i;++j)
        {
            if(arr[j]->length>=4)
                continue;
            //聯集後,計算有幾個不為0的位元,即為合併後所需空間
            mask=arr[i]->mask|arr[j]->mask;
            
            /*
            for(count=k=0;k<10;++k)
                if(1<<k&mask)
                    ++count;
            
            if(count>4)//合併後會超過
                continue;
            */
            
            //查表加速,等同於上面註解掉的程式碼
            if(~bit_count[mask/32]>>mask%32&1) //合併後會超過
                continue;
            
            //合併後不會超過的話執行以下程序合併
            for(k=0;k<arr[i]->length;++k)
            {
                mask=1<<arr[i]->buf[k];
                if(!(mask&arr[j]->mask))
                {
                    arr[j]->mask|=mask;
                    arr[j]->buf[arr[j]->length++]=arr[i]->buf[k];
                }
            }
            memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
            --i;
            break;
        }
    }
    //顯示結果
    printf("result:\n");
    showSetArray(n,arr);
    printf("-------------\n\n");
    return 0;
}

void setDatas(set* p, int n, ...)
{
    int x;
    p->length=0;
    va_list args;
    va_start(args,n);
    p->mask=0;
    while(n--)
    {
        x=va_arg(args,int);
        p->buf[p->length++]=x;
        p->mask|=1<<x;
    }
    va_end(args);
}
void showSetArray(int n,set **arr)
{
    int i,j;
    for(i=0;i<n;++i)
    {
        printf("%02X ",arr[i]->mask);
        for(j=0;j<arr[i]->length;++j)
            printf(" %d%c",arr[i]->buf[j],arr[i]->length-1==j?'\n':',');
    }
}
看更多先前的回應...收起先前的回應...
weiclin iT邦高手 4 級 ‧ 2018-11-03 23:41:37 檢舉

不過他的資料是 {4,3,1} {3,5}
所以其實 SetB 不屬於 SetA

淺水員 iT邦新手 5 級 ‧ 2018-11-04 09:21:54 檢舉

如果不存在子集合的關係
就判斷 SetA | SetB 不為 0 的位元數
如果在 4 以內,則表示可以合併
程式碼補上了

weiclin iT邦高手 4 級 ‧ 2018-11-04 12:04:07 檢舉

/images/emoticon/emoticon12.gif

你的程式唯一的問題是
使用了許多老師還沒教到的進階語法
沒法子跟老師解釋
/images/emoticon/emoticon06.gif

fysh711426 iT邦研究生 5 級 ‧ 2018-11-04 16:15:18 檢舉

您的解法好厲害

for(count=k=0;k<10;++k)
    if(1<<k&mask)
        ++count;

if(count>4)//合併後會超過
    continue;

這段程式看懂了,但查表的地方不太清楚邏輯,可以解說嗎 >"<?
/images/emoticon/emoticon32.gif

淺水員 iT邦新手 5 級 ‧ 2018-11-04 18:08:12 檢舉

因為 mask 全部的狀況是 1024 種
可以事先計算每種狀況是否不超過 4 個 bit 被設為 1

一開始直觀的想法是用 int bit_array[1024]; 去儲存這1024種狀況

int bit_array[1024],i;
for(i=0;i<1024;++i)
    if(i 不超過 4 個 bit 是 1)
        bit_array[i]=1;
    else
        bit_array[i]=0;

但是每個整數只會儲存 0 跟 1 而已
因此為了避免浪費空間,可以以一個 bit 代表一組資料
這時需要 1024 位元的儲存空間
(每個 uint32_t 有 32 個位元,共有 32 個 uint32_t,合計 1024 bit)

weiclin iT邦高手 4 級 ‧ 2018-11-04 18:10:28 檢舉

海綿寶寶 那不是更好嗎
/images/emoticon/emoticon39.gif

fysh711426 iT邦研究生 5 級 ‧ 2018-11-04 18:57:16 檢舉

原來是被當成二維陣列,我懂了,感謝您的解說。
/images/emoticon/emoticon37.gif

超厲害的解法!

1
小魚-Aria
iT邦新手 5 級 ‧ 2018-11-03 19:10:42

這是目前想到的直覺想法
如果有更好的方法再請求各路大神提供了 > <
表達能力還有待加強請見諒 /images/emoticon/emoticon02.gif

方法:
除第一列外的每一列都從第一列開始比對元素
如果第一列不包含的該列元素個數多於第一列的空位數,就再往下一列去做比對
如果第一列不包含的該列元素<=第一列的空位數,
就將第一列原本不包含的那幾個元素加入第一列,並移除已經合併的該列
如果在找到該列位置之前都沒有符合條件可以塞進去的列
那就表示該列會自成一列,那就接著將下一列從第一列開始比對,再重複上面的比對動作

column = 4
for (i = 1 ~ (Array.size - 1)){
    for ( j = 0 ~ (i - 1)){
        if ((num of elements that not in Array[j]) > (column-Array[j].size)){
            j++
            if (j = i) i++
       }   
        else {
            add (elements that not in Array[j]) to Array[j]
            remove Array[i]
            Array.size - 1
            break
       }
    }
}   

以你的例子來說就是
從第一列開始找,找到第 2 列發現元素不滿 4 個
就將第 2 列 {4,3,1} 從第一列 {1,2,3,6} 開始比對元素
發現不包含的元素(也就是 4)個數是 1 > 第一列的空位個數 0,
因此在第 2 列之前沒找到符合條件可以塞進去的,所以自成一列,

接著將第 3 列 {5,4,1,2} 從第一列 {1,2,3,6} 開始比對,
發現不包含的元素(5,4)個數 2 > 第一列空位 0,
因此往下跟第 2 列 {4,3,1} 做比對,發現不包含的元素(5,2)個數 2 > 第2列的空位數 1 ,
因此在第 3 列之前沒有符合的,所以自成一列

接著將第 4 列 {3,5} 從第一列 {1,2,3,6} 開始比對,
發現不包含的元素(5)個數是 1 > 第一列的空位個數 0,
因此往下跟第 2 列 {4,3,1} 做比對,發現不包含的元素(5)個數 1 = 第2列的空位數 1 ,
因此將 5 加入第 2 列,並且移除第 4 列。

接著將現在的第 4 列 (也就是原本的第 5 列) {3,4} 從第一列 {1,2,3,6} 開始比對,
發現不包含的元素(4)個數是 1 > 第一列的空位個數 0,
因此往下跟第 2 列 {4,3,1,5} 做比對,發現不包含的元素個數 0 = 第2列的空位數 0 ,
將不包含的元素加入(這次沒有不包含的元素),移除第 4 列。

看更多先前的回應...收起先前的回應...

你寫的很清楚
可是你沒看到樓主下的 tag
是 c (最早的版本是 #c, 現在是 c, 不知道還會不會改)

我有看到是 c ~~
可是我不會寫 c /images/emoticon/emoticon20.gif
所以只能用文字和類似 pseudo code 的方式表達演算法 > <

小魚謝謝你,真的講得很詳細,我想想看要如何用C呈現

淺水員 iT邦新手 5 級 ‧ 2018-11-03 20:26:31 檢舉

問一下數字是只有0-9嗎?

不謝不謝~~
只是提供一下我的想法而已 > <
順便想看看有沒有大神有更好的最佳解ˊˇˋ

回樓上~~
我不知道原PO的需求數字範圍是多少~
不過這個方法應該是都適用~
(有錯的話請糾正 > <)

數字可介於0~9

0
sx0800
iT邦新手 5 級 ‧ 2018-11-04 07:54:09

看敘述是,
先拆成1維陣列,再4個一組放進2維陣列。

1
wwx
iT邦研究生 1 級 ‧ 2018-11-04 10:18:40

我去下載了
Pelles C (http://www.pellesc.de/)
同大家的想法,只是純C寫要寫比較多而已...
寫一個比較蠢的實例供參考

#include <stdio.h>
int InList(char a, char x[4])
{
	int k;
	for (k = 0; k < 4; k++)
	{
		if (a == x[k])
			return 1;
	}
	return 0;
}
int GetCount(char x[4])
{
	int k;
	for (k = 0; k < 4; k++)
	{
		if (x[k] == 0)
			return k;
	}
	return 4;
}
int GetSpace(char x[4])
{
	return (4 - GetCount(x));
}
void Compress(char t[4], char x[4])
{
	int i, k;
	for (i =0; i < 4; i++)
	{
		if (t[i] == 0)
			break;
		if (InList(t[i], x))
			t[i] = 0;
		else
		{
			x[GetCount(x)] = t[i];
			for (k = i; ++k < 4;)
			{
				t[k-1] = t[k];
				if (t[k] == 0)
					break;
			}
			i--;
		}
	}
}
void ShowArray(char a[5][4])
{
	int i, j;
	for (i = 0; i < 5; i++)
	{
		printf("a[%d]=", i);
		for (j = 0; j < 4; j++)
			printf("%c%d", (j==0)?'{':',', a[i][j]);
		printf("}\n");
	}
}
int main(int argc, char *argv[])
{
	char a[5][4]={
		{1,2,3,6},
		{4,3,1,0},
		{5,4,1,2},
		{3,5,0,0},
		{3,4,0,0}
	};

	int i, j, k;
	int count, need;
	
	printf("Origin:\n");
	ShowArray(a);
	
	for (i = 1; i < 5; i++)
	{
		for (j = 0; j < i; j++)
		{
			k = 0;
			need = 0;
			count = 0;
			for (k = 0; k < 4; k++)
			{
				if (a[i][k] == 0)
					break;
				if (InList(a[i][k], a[j]))
					count++;
				else
					need++;
			}
			if (need > 0)
			{
				if (need <= GetSpace(a[j]))
				{
					Compress(a[i], a[j]);
				}
			}
			else if (count == GetCount(a[i]))
			{
				while (k > 0)
					a[i][--k] =0;
			}
		}
	}

	printf("Compressd:\n");
	ShowArray(a);
	
	return 0;
}

https://ithelp.ithome.com.tw/upload/images/20181104/2007154535gRii9sP4.png

請不要選我正解

0
a30309598
iT邦新手 5 級 ‧ 2018-11-05 11:21:53

用C寫的,我的做法比較直覺,二維轉一維,再轉回二維。
arr1即是答案

#include<stdio.h>
#include<stdlib.h>

int main()
{
	char temp[100] = {'\0'};
	int arr1[5][4];
	int arr2[5][4] = { 
		{ 1,2,3,6 },
		{ 4,3,1 },
		{ 5,4,1,2 },
		{ 3,5 },
		{ 3,4 } 
	};

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if(arr2[i][j]==0)
				sprintf_s(temp, "%s%c", temp, 'x');
			else 
				sprintf_s(temp, "%s%d", temp, arr2[i][j]);
		}
	}

	int row = 0, column = 0;
	for (int count = 0; count < 100; count++)
	{
		if (temp[count] != 'x')
		{
			if (column == 4)
			{
				column = 0; row++;
			}
			if (row == 5)
				break;

			arr1[row][column] = temp[count] - 48; //char to int
			column++;
		}
	}
	
	system("pause");
	return 0;
}

我要發表回答

立即登入回答