從集合中生成所有可能的有序子集

我知道如何從一個包含位混合的集合中生成所有可能的子集。例如，從集合中生成所有可能的有序子集

//Get if nth position's bit is set 
bool IsBitSet(int num, int bit) 
{ 
    return 1 == ((num >> bit) & 1); 
} 

int subsetMaxIterCount = pow(2, someList.size()); 
for (int i = 0; i < subsetMaxIterCount; i++) { 
    vector<A> subset; 
     for (size_t i = 0; i < jobList.size(); i++) 
     { 
      if (IsBitSet(jobSubsetIdx, i)) { 
       //Add to subset here 
      } 
     } 

     //Here we have a subset for some i 
    }

但是，這並沒有考慮到排序。

例如，如果我有一個集合{1，2，3}，上述算法生成的子集：

{}，{1}，{2}，{3}，{1， 2}，{1,3}，{2,3}，{1,2,3}

我需要在現實中是這樣

{}，{1}，{2}，{3 }，{1,2}，{1,3}，{2,3}，{1,2,3}，{2,1}，{2,1,3}，{2,3,1}， {3,1}，{3,2}，{3,1,2}，{3,2,1}

不確定以上列表是否詳盡。生成這樣的東西的有效算法是什麼？（這是所有可能的子集與順序排列的方式？）

來源

2016-11-07 Xiagua

是的。生成子集，然後爲每個子集生成排列。 –

std :: next_permutation和std :: prev_permutation – pat

投票關閉，因爲缺乏可重複的示例 –

我們使用位twiddling生成子集的方式，每個子集在其中排序e.g. {1, 2, 3}, {2, 3}, {1, 3}。您可以使用next_permutation

vector<vector<int>> mySubsetGenerator(vector<vector<int>>& subsets) { 
    vector<vector<int>> extendedSubset; 
    for(int i = 0; i < subsets.size(); ++i) { 
     do { 
      extendedSubset.push_back(subsets[i]); 
     } while(next_permutation(subsets[i].begin(), subsets[i].end())); 
    } 
    return extendedSubset; 
}

此外，你可以只使用回溯採取陣列中的一個或多個元素來生成所有可能的排列生成每個子排列。

來源

2016-11-07 05:03:21

從集合中生成所有可能的有序子集

回答

相關問題