iT邦幫忙

5

c/c++語言: 用多個for迴圈窮舉陣列的數字,有什麼好方法化簡嗎? #保證給最佳解答

c++

哈囉~ 大家好,
我發現iT邦幫忙的問答區非常多人是不給最佳解答的,
我覺得這樣並不是很好,
有些發問者回答的盡心盡力,
應該給予「最佳解答」表達基本的感謝與鼓勵

因此在發問前,
我先保證只要有人回答,
哪怕是回答隻字片語或提供想法,
我一周內一定會給出「最佳解答」

問題描述

假設我有一個int陣列,裡面有四個元素(更廣義的),
每個元素的值可能在2~5之間(更廣義的問題: 每個元素的值可能在a~b之間)
我需要窮舉所有可能的陣列,
一個很直接的方法便是寫四個for迴圈窮舉它,
範例如下:

#include <iostream>
using namespace std;

//函數功能: 單純把陣列的前n個數印出來做測試
void printArray(int* array, int n)
{
    for (int i = 0; i < n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(void)
{
    int array[4];
    int A, B, C, D;
    for(A=2; A<=5; A++)
        for(B=2; B<=5; B++)
            for(C=2; C<=5; C++)
                for(D=2; D<=5; D++)
                {
                    array[0] = A;
                    array[1] = B;
                    array[2] = C;
                    array[3] = D;
                    printArray(array, 4);
                }
    return 0;
}

但我覺得這樣並不是個很好的寫法,
原因是廣義的問題我們可以問:

我有一個int陣列,裡面有n個元素,
每個元素的值可能在a~b之間,
如何窮舉所有可能的陣列?

照這個寫法,
那麼如果n是8的話,
我們就需要寫8個for迴圈,
程式會過於冗長,
而且無法處理n是變數的情形,
不知道大家是否有好的方式化簡這樣多個for迴圈?

我是知道如果在python語言中的話,
可以直接用內建的itertools模組裡的product就解決了 (見Python官方文檔- itertools),
想問如果必須在c++語言寫的話,
有沒有什麼好的寫法呢?

心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:02:20 檢舉
嗨,大家好~
非常感謝大家熱心的回答,
一級屠豬士的解答最接近我想問的功能,
頒發最佳解答給他
9
一級屠豬士
iT邦大師 1 級 ‧ 2020-05-14 23:40:36
最佳解答

做這種事,函數式語言比較有優勢. SQL 更是好用.

https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

可以看裡面 Haskell ,OCaml, 還有 Python 裡另外使用 Applicative functor 的部分.
當然也有 C/C++ 等程序性語言.

心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:02:51 檢舉

謝謝,網頁解說的蠻清楚的~

1

一般多層級的for。我大多是採用callback。而不是backcall

不過我不太了解c語言。基本方式為

X = callfunc(...);

function callfunc(...){
   //判斷再call
   X = callback(...);
   return X;
}

心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:03:25 檢舉

謝謝分享想法~

1
japhenchen
iT邦大師 1 級 ‧ 2020-05-15 08:50:23

在C#或其他OBJECT-C或JAVA中,都是用

    foreach( var item in array )
    {
        item = 1
        Console.WriteLine(item);
    }       

在python裡也類似

    for item in array:
        item = 1
        print(item)
心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:05:05 檢舉

其實不太接近我想問的(因為這樣應只能固定把array裡的元素設成同一個數,無法達到每個元素都是有範圍的窮舉),但還是謝謝你的分享~

大不了在裡面多一個遞增值

   ccc = 1
   for item in array:
        item = ccc
        print(item)
        ccc += 1 

2
海綿寶寶
iT邦大神 1 級 ‧ 2020-05-15 09:10:27

比起答案
問題本身更重要

這問題就我的解讀,若以 SQL 來類比的話
就是用SELECT * FROM EMPLOYEE去窮舉出所有資料
有沒有比較簡化的寫法

我的答案是沒有
因為題目就是 list all (full table scan 是無法簡化的)

之所以會這麼寫的原因
通常是在解動態規劃的題目時使用的暴力解決法

但其實樓主早就不用暴力解決法解動態規劃的題目
自然不需要做這種窮舉的事

所以回到原點
這個問題的本質是什麼
就是「工作太閒,純嗑牙」之用

大家週末愉快
/images/emoticon/emoticon73.gif

另外
請教一下 python 高手
python 的 itertools
是只能處理排列組合(n 個元素組合來組合去)
還是可以處理本題目的(n 個元素,每個元素還是 a-b 值,然後再組合來組合去)
/images/emoticon/emoticon19.gif

心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:09:38 檢舉

嗨嗨,已經有網友分享解答了,
或許窮舉的內容無法化簡,
但是for迴圈是可以化簡不用這麼多個的
(避免若陣列中有8個元素,就真的要寫8個for迴圈)

另外回答一下,python 的 itertools
可以處理本題的「n 個元素,每個元素是 a-b 值」(俗稱Cartesian product),
亦能夠處理n個元素取一部分出來排列或組合

2
淺水員
iT邦研究生 2 級 ‧ 2020-05-15 10:32:14

下面這個 class 可以產生不同的 index 所有組合
後續可以依據 index 輸出不同的元素
所以產生的組合並不限定在某個資料型態

#include<vector>

class StatusManger
{
private:
	std::vector<int> status;
	std::vector<int> limits;
public:
	void push(int n);
	void init();
	bool next();
	int get(int x);
	int size();
};

void StatusManger::push(int n)
{
	limits.push_back(n);
}

void StatusManger::init()
{
	status.clear();
	for(int i=limits.size();i>0;--i) {
		status.push_back(0);
	}
}

bool StatusManger::next()
{
	int carry=1,
	    current=0,
		n=limits.size();
	while(carry && current<n) {
		if(status[current]+1<limits[current]) {
			++status[current];
			carry=0;
		} else {
			status[current]=0;
		}
		++current;
	}
	return carry==0?true:false;
}

int StatusManger::get(int x)
{
	if(x<0 || x>=status.size()) {
		return -1;
	}
	return status[x];
}

int StatusManger::size()
{
	return limits.size();
}

使用範例一:印出 4 層 2~5

int main()
{
	StatusManger sm;
	sm.push(4); //第一層,會產生 0~3
	sm.push(4); //第二層,會產生 0~3
	sm.push(4); //第三層,會產生 0~3
	sm.push(4); //第四層,會產生 0~3
	int n=sm.size(); //取得共幾層
	sm.init(); //初始化狀態
	do{
		for(int i=0;i<n;++i) {
			//輸出時加上2就可以了
			std::cout<<sm.get(i)+2;
		}
		std::cout<<std::endl;
	}while(sm.next()); //如果還有下一個 next 會回傳 true 並更新狀態
	return 0;
}

使用範例二:不同字元的組合

int main()
{
	const char* strArr[3]={"xyz", "1234", "AB"};
	StatusManger sm;
	sm.push(strlen(strArr[0]));
	sm.push(strlen(strArr[1]));
	sm.push(strlen(strArr[2]));
	int n=sm.size();
	sm.init();
	do{
		for(int i=0;i<n;++i) {
			std::cout<<strArr[i][sm.get(i)];
		}
		std::cout<<std::endl;
	}while(sm.next());
	return 0;
}
心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:13:29 檢舉

嗨嗨,謝謝你的程式分享,
我覺得你寫的也蠻不錯的,
只是「最佳解答」只能給一個,
這邊仍表達感謝之意
/images/emoticon/emoticon41.gif/images/emoticon/emoticon41.gif

1
CP-Y
iT邦新手 5 級 ‧ 2020-05-15 11:21:59

雖然我不是寫C++的,小試了一下遞迴版。

#include <iostream>

using namespace std;

// 輸出
void printArray(int* array, int n)
{
    for (int i = 0; i < n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

// 遞迴式
void Trace(int min, int max, int length, int index, int* arr)
{
    // 根據長度初始化
	if(arr == NULL) 
	{
		int array[length];
		for (int i = 0; i < length; i++)
			array[i] = min;

		arr = array;
	}
    
	// 遞迴結束點
	if(index >= length)
	{
		printArray(arr, length);
		return;
	}
	
	for (int j = min; j <= max; j++)
	{
    	arr[index] = j;
    	Trace(min, max, length, index + 1 ,arr);
	}
} 

int main()
{
	int length = 4;
	int min = 2;
	int max = 5;
	printf("min = %d, max = %d, length = %d\n", min, max, length);
	Trace(min, max, length, 0, NULL);
    return 0;
}
心原一馬 iT邦研究生 5 級 ‧ 2020-05-15 11:26:34 檢舉

謝謝分享另一種想法~
寫的蠻不錯的 ^^

淺水員 iT邦研究生 2 級 ‧ 2020-05-15 12:10:01 檢舉

其實這就是「深度優先搜尋

我要發表回答

立即登入回答