排列組合

排列組合就是一組數字或文字，其中元素依排列位置的不同，而產生的組合。

例如若有一組數列 1、2、3，若增加一個 5，在不改變 1、2、3 順序的情況下，5 可以放在前面、中間或後面，所以可能產生 5 1 2 3，1 5 2 3，1 2 5 3，1 2 3 5 四種組合，也就是在特定 n 個元素排列的條件下，每增加一元素，就會產生 n+1 種新的排列組合。

#include <iostream>

void Permutations(int *list, int n, int x)
{
    for(int i=0; i<= n; i++) //因為多一個元素，所以執行n+1次 
    {
      for(int j=0; j<n; j++) //只列出原始list，多的由 if 處理 
      {
            if(j==i)
                 std::cout << x << " "; 
            std::cout << list[j] << " "; 
      }
      if(i==n) //最後一次 
         std::cout << x;

      std::cout << std::endl;     
    } 
} 

int main()
{
int list[] = { };
Permutations(list, 0, 100);

int list1[] = { 1 };
Permutations(list1, 1, 200);

int list2[] = { 1,2 };
Permutations(list2, 2, 300);
    
int list3[] = { 1,2,3 };
Permutations(list3, 3, 400);

return 0;

}

執行結果

數列 (1) 的排列組合只有 1 種 {1}，而數列 (1 2) 的排列組合，就等於把 2 插入數列 (1 ) ，而得到 {1 2} 和 {2 1}。若對數列 (1 2) 的每種排列組合再增加一個 3，就得到 {3 1 2} {1 3 2} {1 2 3} 及 {3 2 1} {2 3 1} {2 1 3}，即為3個元素的全排列，其項數為 3*2*1=6，4個元素的項數為 4*3*2*1=24... 故 n 個元素的全排列，其項數為 n! 個。

以大風吹的方式看 {1 2 3}，以 1 分別與 2、3 交換位置，可以得到 {2 1 3} 和 {3 2 1} 這兩種排列結果，接著再把{2 3} 交換位置得到 {1 3 2}，同理由 {2 1 3} 和 {3 2 1} 又可得到 {2 3 1} 和 {3 1 2}。

所以全排列就是從第一個元素起，每個元素分別與後面的元素交換位置，適合以遞迴的方式撰寫程式

#include<iostream>

template <typename T>

void swap(T& a, T& b)

{

  T c(a);

  a=b;

  b=c;

}

template <typename T>

void perm(T* list,int start,int length)

{

if(start == length-1)

{

for(int i=0; i<length; i++)

std::cout << list[i] << " ";

std::cout << std::endl;

}

else

{

for(int i=start; i<length; i++)

{

swap(list[start],list[i]); 

perm(list,start+1,length);

swap(list[start],list[i]); 

}

}

}

int main()

{

    int list[] = {1,2,3,4};

    perm(list,0,4);

    return 0;

}

在某些不同的情況，{1 2 3} 需要展開成 {1} {2} {3} {1 2} {1 3} {2 3} {1 2 3} 等項目，例如在檢視購物清單，希望統計 1 2 3 三樣產品的購買記錄和相關性時。

上述需求為描述此 3 個元素 "有" 和 "無" 的組合，而 2 進位就是以 0 與 1 來呈現每一位數的值，故可以藉由 2 進位的對應 000 001 010 011 100 101 110 111 來展開項目組合

#include<iostream>

int pow2(int n)

{

    int r=1;

    while(n-- > 0)

        r*=2;

    return r;

}

template <typename T>

void spreadout(T* list, int len)

{

    int items=pow2(len)-1;

    T newlist[items][len];

    

    for(int i=0; i<items; i++)

    {

        int pos=0, idx=0;

        int binary=i+1;

        while(binary)

        {

            if(binary & 1)

                newlist[i][idx++]=list[pos];

            binary=binary/2;

            pos++;

        }

        

        for(int j=0; j<idx; j++)

        std::cout << newlist[i][j] << " ";

        std::cout << std::endl;

    }

}

int main()

{

    int list[] = {1,2,3,4};

    spreadout(list,4);

    return 0;

}

執行結果