matlab如何產生只有0與1的長度為n的所有不重複序列？

01-28

matlab如何產生只有0與1的長度為n的所有不重複序列，求複雜度不高，計算量不大的方法，matlab還處於學習摸索階段，也不知道有無較為快捷的函數

如果你要從排列組合的角度來看比較繁瑣：

首先，你需要決定 $n$ 個位置上總計填充多少個 $1$ ，比如假定填充 $i$ 個（顯然 $0le ile n$ ），剩餘位置填充 $0$ .
其次，你需要決定從 $n$ 個位置中選出哪 $i$ 個位置用於填充 $1$ ，顯然有 $C_n^i$ 中情況.
最後，統計出 $i=0, 1,cdots, n$ 的所有結果即可。

MATLAB自帶nchoosek之類的函數，方便實現，但是對於比較大的 $n$ 來說，因為總計有 $2^n=C_n^0+C_n^1+cdots+C_n^n$ 種情況，內存佔用會比較大，但是測試了下 $nle 16$ 基本都能秒出答案，更大的數則要反應一會兒了。

PS.謹慎測試 $n$ 比較大的情形，沒準會卡成翔，對應實驗室2GB的RAM向來都是捉襟見肘......

function results = binGenerator(n) % BINGENERATOR output all the possible permutations of n digits % consisted of 0 and 1.

results = repmat(0, 2^n, n); %初始化結果矩陣，每一行（代表一種可能情況）為n個零 idx = 1; for i = 0:n iCns = nchoosek(1:n, i); %nchoosek 從n個元素中無順序選出k個，窮盡所有可能情況 for j = 1:size(iCns, 1) results(idx, iCns(j, :)) = 1; idx = idx + 1; end end end

&>&> binGenerator(4)


ans =

0000 1000 0100 0010 0001 1100 1010 1001 0110 0101 0011 1110 1101 1011 0111 1111

------------------------------------------------------------------------------------------------------------------------------------------

「但我真正想說的還是換個角度思考問題]

$n$ 個位置，每個位置插入 $0|1$ ，最後每一種結果都和一個二進位數唯一對應（再顯然不過了），比如排列結果若為 $001100$ （假設 $n=6$ ），其對應的二進位數就是 $2^3+2^2=12$ ，所以我們只需要將 $0 ightarrow2^n-1$ 轉碼為二進位形式就能得到結果：

&>&> dec2bin(0:(2^4-1), 4) % dec2bin可以將十進位數轉為二進位字元串，還能定製輸出長度


ans =

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

簡單一行就能輸出第一種方案的結果，而且還很好理解，對於 $n$ 位的操作，只需將 $4$ 替換為 $n$ 即可。

我對@yellow的第二個答案做了一些小的調整，可以直接生成相應的數據：

abs(dec2bin(0:(2^n-1), n))-48 % 其中n為長度


&>&> C = abs(dec2bin(0:(2^4-1), 4))-48, whos
C =
     0     0     0     0

     0     0     0     1

     0     0     1     0

     0     0     1     1

     0     1     0     0

     0     1     0     1

     0     1     1     0

     0     1     1     1

     1     0     0     0

     1     0     0     1

     1     0     1     0

     1     0     1     1

     1     1     0     0

     1     1     0     1

     1     1     1     0

     1     1     1     1
  Name       Size            Bytes  Class     Attributes

C 16x4 512 double

在此基礎上我也做了相應的拓展：

如果你想用0,1,...,a-1，進行排列組合，並且其長度為n，為了方便描述，以0,1,2 進行排列組合，其長度為4：

首先：確定轉化的進位數，進位數為a = 3；
其次：確定長度在a進位數下的最大值，並將其轉換成10進位，進位為3長度為4的最大值為2222，其相應10進位數為80
再次：生成在10進位數下0到最大值間隔為1的數組，0,1,2,...,80;
然後：將生成的10進位數組轉換成a進位數的數；
最後：將其轉換成ASCII碼並減去48，就可以獲得想要的排列組合了。

優點：長度n在a進位數下的最大值可以確定將要進行組合的個數，避免了不會用排列組合數的公式進行計算組合的個數。

說明：1. 本方法僅用於a &< n ；

2. 最後一步-48主要是為了將ASCII碼轉換成對應的數字值。

abs(dec2base(0:base2dec(repmat(num2str(a-1),1,n),a), a,n))-48


% 0,1 進行排列組合，其長度為4:

&>&> a = 2;n = 4;

&>&> C = abs(dec2base(0:base2dec(repmat(num2str(a-1),1,n),a), a,n))-48,whos
C =
     0     0     0     0

     0     0     0     1

     0     0     1     0

     0     0     1     1

     0     1     0     0

     0     1     0     1

     0     1     1     0

     0     1     1     1

     1     0     0     0

     1     0     0     1

     1     0     1     0

     1     0     1     1

     1     1     0     0

     1     1     0     1

     1     1     1     0

     1     1     1     1
  Name       Size            Bytes  Class     Attributes

C 16x4 512 double

首先確定共有2∧n個這樣的序列，然後用zoros函數生成n×2∧n的矩陣。從第一列開始，遞歸得用二分的方法將改為0 1。演算法複雜度為O(n！)

如果寫好點應該可以壓縮到O（nlogn）