一道演算法題，很難，求大神？

01-11

要求時間複雜度盡量低，結果給出a1到a13所有可能的組合

將題中三個式子按順序分別編號為 (1)，(2)，(3)。(1)+(2)+(3) 得：

(4) a1+a2+a3+2a4-2a5+2a6+2a7+a8+a9+a10+a11+a12+2a13=126

a1 到 a13 必為 1 到 13 這 13 個數的某種排列，因此有：

(5) a1+a2+...+a13=1+2+...+13=91

(4)-(5)可得：

(6) a4+a5+a6+a7+a13=35

將(6)分別代入(1)、(2)和(3)，得：

(7) a1+a3-a4-a5+a12=7

(8) a9+a11-a13=7

(9) a2-a6-a7+a8+a10=7

觀查(1)、(2)、(3)、(7)、(8)、(9)可發現某些變數總是一起以加法形式出現，因此這些變數可以用一個變數代替表示。令：A=a1+a3+a12, B=a2+a8+a10, C=a4+a5, D=a6+a7,

E=a9+a11, F=a13，得：

(1) -&> A+D+F=42

(2) -&> C+D+E=42

(3) -&> B+C+F=42

(7) -&> E-F=7

(8) -&> A-C=7

(9) -&> B-D=7

求出上麵線性方程組的基礎解系（Reshish Matrix Calculator），得：

(10) A=42-D-F

(11) B=7+D

(12) C=35-D-F

(13) E=7+F

顯然，此方程組的可行解集即原題的可行解集。其中 A、B、(D+F) 均為原方程組 3 個變數之和，C、E 為 2 個變數之和。令原方程組中 3 個變數構成一個三元組，2 個變數構成一個二元組。那麼一個可行解由 3 個三元組和 2 個二元組構成（&，&，&，&和&），並滿足其中任兩個元組之間不存在相同的數以及各元組的和滿足上面的方程組。

一個元組可用 2 個位元組（即 16 位）的整數表示，第 i 位為 1 表示此元組中包含 i，我們稱這整數為元組的指紋。例如 37 二進位為 100101，表示元組 &<1 3 6&>。根據該定義可在枚舉可行解前進行預處理：枚舉所有滿足約束的 C(13,3)=286 個三元組和 C(13,2)=78 個二元組，建立各元組的和到指紋的映射 f。注意 f 是一對多的映射，即多個不同的元組可能有相同的和，例如&<4 7 9&>和&<3 6 11&>。

接下來開始枚舉可行解。首先在滿足 (12) 的前提下枚舉可行的 F 和 D，並解方程組求出 A、B、C 和 E 的值。然後根據映射 f 枚舉出所有可行的其它 4 個元組。注意， 2 個元組的指紋按位與若不為零即存在交集，不能構成可行解。最後對 A、B、C、D 和 E 這 5 個元組分別進行「各自內部的」全排列，即得到所有可行解。

此外，時間複雜度是相對輸入數據的規模而言，這種所有數據都固定不變的演算法的時間複雜度永遠是 O(1)。要是改成「運算時間儘可能少」就比較嚴謹了。按上述演算法計算，運算時間一定遠遠小於將結果輸出到屏幕所花的時間。

樓下其它演算法都是枚舉 1 到 13 的所有排列，然後檢查每一種排列是否滿足方程組。而我的方法是先解出滿足方程組的可行解集，再去枚舉能夠「覆蓋」1 到 13 的所有排列。顯然此方法的運算次數要少得多。

我沒說清的地方，或評論或私信，千萬別帶著問題離開。

自我感覺水平太菜，除了遍歷試錯外，沒想到任何討巧的演算法。但還是要佔個茅坑，證明我來過Org

先用C++的全排列一個個試錯，代碼簡單，但耗時接近1分鐘。

#include & #include & #include &


int main()

{

    clock_t t1 = clock();

    unsigned n = 0;
    unsigned a[14] = { 0, 1,2,3,4,5,6,7,8,9,10,11,12,13 };

    do {

        if( a[1]+a[3]+a[6]+a[7]+a[12]+a[13] == 42

             a[4]+a[5]+a[6]+a[7]+a[9]+a[11] == 42

             a[2]+a[4]+a[5]+a[8]+a[10]+a[13] == 42 )

            ++n;

    } while( std::next_permutation(a+1,a+14) );

clock_t t2 = clock(); printf( "%u ", n ); printf( " ---- %ld.%03ld --- ", (t2-t1)/CLOCKS_PER_SEC, (t2-t1)%CLOCKS_PER_SEC ); // 輸出 1292544, 耗時 58.203 秒 return 0; }

再將樓主的方程組化簡一下，用最老土的for來做，以下C代碼耗時接近半秒，但代碼混亂

#define FORLOOP(an) for( unsigned an=1; an&<=13; ++an ) { if( mask (1u&<&13 || (mask(1u&<& #include &


int main()

{

    unsigned n = 0;

    clock_t t1 = clock();
    unsigned mask = 0;

    FORLOOP( a9 )

        FORLOOP( a11 )

            JUDGE( a13, a9+a11-7 )

                FORLOOP( a1 )

                    FORLOOP( a3 )

    /**************/    FORLOOP( a4 )

    /* 原方程組化簡為 */    FORLOOP( a5 )

    /* a9+a11-a13 == 7    */    JUDGE( a12, 7-(a1+a3-a4-a5) )

    /* a1+a3-a4-a5+a12 == 7   */    FORLOOP( a2 )

    /* a2-a6-a7+a8+a10 == 7       */    FORLOOP( a6 )

    /*                                */    FORLOOP( a7 )

    /* 輸出 1292544                       */    FORLOOP( a8 )

    /* 耗時 0.468秒                           */    JUDGE( a10, 7-(a2-a6-a7+a8) )

    /**********************************************/    ++n;

    }    }    }    }    }    }    }    }    }    }    }    }    }

clock_t t2 = clock(); printf( "%u ", n ); printf( " ---- %ld.%03ld --- ", (t2-t1)/CLOCKS_PER_SEC, (t2-t1)%CLOCKS_PER_SEC ); return 0; }

考慮到「a9 a11 可互換，a1 a3 a12 可互換，a4 a5 可互換，a2 a8 a10 可互換，a6 a7 可互換」後，代碼還可以優化，優化後運行時間小於 1毫秒，用標準C函數無法計時了。

#define FORLOOP(begval,an) for( unsigned an=begval; an&<=13; ++an ) { if( mask (1u&<& e2 ) break; if( an&<1 || an&>13 || (mask(1u&<& #include &


int main()

{

    unsigned n = 0;

    clock_t t1 = clock();
    unsigned mask = 0;

    FORLOOP( 1, a9 )

        FORLOOP( a9+1, a11 )

            JUDGE( 0,0, a13, a9+a11-7 )

                FORLOOP( 1, a1 )

                    FORLOOP( a1+1, a3 )

    /**************/    FORLOOP( a3+1, a12 )

    /* 原方程組化簡為 */    FORLOOP( 1, a4 )

    /* a9+a11-a13 == 7    */    JUDGE( a4,a5, a5, a1+a3+a12-a4-7 )

    /* a1+a3+a12-a4-a5 == 7   */    FORLOOP( 1, a2 )

    /* a2+a8+a10-a6-a7 == 7       */    FORLOOP( a2+1, a8 )

    /*                                */    FORLOOP( a8+1, a10 )

    /* 輸出 1292544                       */    FORLOOP( 1, a6 )

    /* 耗時 0.000秒                           */    JUDGE( a6,a7, a7, a2+a8+a10-a6-7 )

    /**********************************************/    n += 2*6*2*6*2;

    // 因為[a9 a11 可互換] [a1 a3 a12 可互換] [a4 a5 可互換] [a2 a8 a10 可互換] [a6 a7 可互換]，所以加上2*6*2*6*2

    }    }    }    }    }    }    }    }    }    }    }    }    }

clock_t t2 = clock(); printf( "%u ", n ); printf( " ---- %.3f --- ", (t2-t1+0.0)/CLOCKS_PER_SEC ); return 0; }

太簡單了。用集合差，交得分組然後排列組合既可。思路，每式6個元素，平抅值7。將1---13按（1，13）（2，12）分組.........從已知三式可推知分組，再對分組做排列組合既可。高中知識三分鐘

這題真不錯。。。。

眼睛求解得到未知數的下標就是一組答案，換成線性方程組的觀點，這個下標組成的解就是方程的特解

然後再求這個方程的通解。

之後要是要求解是整數就挨個找一遍就好了。

要求解屬於R那就算了。。。。。。

回溯或者母函數可以求這種排列組合問題

演算法上面沒有什麼高見。解法如下：

首先按未知量重複出現和不重複出現分成兩類，並且化簡式子：

a9 + a11 = 7 + a13

a2 + a8 + a10 = 7 + a6 + a7

a1 + a3 + a12 = 7 + a4 + a5

為了方便起見把下標改寫成1~13:

a1 + a2 = 7 + a3

a4 + a5 + a6 = 7 + a7 + a8

a9 + a10 + a11 = 7 + a12 + a13

然後用回溯演算法。

import java.util.*;


public class RecursiveBackTrack {
	public void solve(int printLimit){

		int[] g = new int[14];

		for(int i = 0; i &< 14; i++){
			g[i] = -1;
		}

		Set& remain = new HashSet&();

		for(int i = 1; i &<= 13; i++){
			remain.add(i);
		}

		long start = System.currentTimeMillis();
		int total = solveRec(g, 1, remain, printLimit);
		long elapsed = System.currentTimeMillis() - start;
		System.out.println("total solutions count: " + total * 2 * 6 * 2 * 6 * 2);
		System.out.println("time elapsed: " + elapsed + " milliseconds");
	}

	private int solveRec(int[] g, int i, Set& remain, int printLimit){

		if(i == 14){

			if(printLimit &> 0){

				printSolution(g);

			}

			return 1;

		}
		int tryValue;

		int count = 0;
		for(tryValue = 1; tryValue &<= 13; tryValue++){
			if(remain.contains(tryValue)  checkGoodCandiate(g, i, tryValue)){
				g[i] = tryValue;
				remain.remove(tryValue);
				int numSolutions = solveRec(g, i + 1, remain, printLimit);
				count += numSolutions;
				printLimit -= numSolutions;
				remain.add(tryValue);
				g[i] = -1;
			}
		}

		return count;
	}

	private boolean checkGoodCandiate(int[] g, int i, int tryValue){
		if(i == 3){
			return tryValue == g[1] + g[2] - 7;
		} else if(i == 8){
			return (tryValue == g[4] + g[5] + g[6] - 7 - g[7])  (tryValue &> g[7]);

		} else if(i == 13){

			return (tryValue == g[9] + g[10] + g[11] - 7 - g[12])  (tryValue &> g[12]);

		} else if(i == 1 || i == 4 || i == 9 || i == 7 || i == 12){

			return true;

		}
		return tryValue &> g[i - 1];

	}

private void printSolution(int[] g){ for(int i = 1; i &<=13; i++){ System.out.print(g[i] + " "); } System.out.println(); } public static void main(String[] args) { int limit = Integer.MAX_VALUE; if(args.length &> 0){ limit = Integer.parseInt(args[0]); } new RecursiveBackTrack().solve(limit); } }

運行結果：

&>java RecursiveBackTrack 20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

total solutions count: 1292544

time elapsed: 74 milliseconds

係數矩陣的增廣矩陣，求非齊次線性方程組的解，要求a13能被a1線性表出。