Library function for Permutation and Combination in C++
Combinations: from Mark Nelson's article on the same topic we have next_combination
Permutations: From STL we have std::next_permutation
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
C++ all arrangements of a set of strings
Your example shows that you want to not only output each subset of your input (the Power set) but also all permutations of each set.
I am not aware of a particular term used for this, but OEIS A000522 calls these "arrangements".
To get what you need, you have to essentially combine your code with Jarod's partial answer (or any of the other power set implementations you can find around here):
void outputAllPermutations(std::vector<std::string> input)
{
// assert(std::is_sorted(input.begin(), input.end()));
do
{
for (std::string s : input)
std::cout << s << " ";
std::cout << std::endl;
} while (std::next_permutation(input.begin(), input.end()));
}
bool isBitSet(unsigned bitset, std::size_t i)
{
return (bitset & (1 << i)) != 0;
}
void outputAllArrangements(const std::vector<std::string>& input)
{
// assert(std::is_sorted(input.begin(), input.end()));
// assert(input.size() < std::sizeof(unsigned) * 8);
unsigned bitset = 0;
std::vector<std::string> subset{};
subset.reserve(input.size());
for (unsigned bitset = 0; bitset < (1 << input.size()); ++bitset)
{
subset.clear();
for (std::size_t i = 0; i != input.size(); ++i)
if (isBitSet(bitset, i))
subset.push_back(input[i]);
outputAllPermutations(subset);
}
}
Demo including example output
I used an unsigned
instead of std::vector<bool>
as I find the overall incrementation logic much easier to reason about that way. This theoretically "limits" the code to inputs smaller than 32 strings (or 64, depending on platform), but seeing as input length 22 would already take thousands of years to output at 1 CPU cycle per output I am comfortable with that.
Given n, generate all permutations of size lesser than 0.5n
For your value "half of N" equal to 3 this would be:
using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))
Note that this is non-allocating so if you want to see the result collect
is required:
julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
[1]
[2]
[3]
[1, 2]
[2, 1]
[1, 3]
[3, 1]
[2, 3]
[3, 2]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Generating N choose K Permutations in C++
The first k values are repeated n-k factorial times. Here is an easy, although inefficient, way to avoid the repetition:
int Factorial(int n)
{
int result = 1;
while (n>1) {
result *= n--;
}
return result;
}
void PermGenerator(int n, int k)
{
std::vector<int> d(n);
std::iota(d.begin(),d.end(),1);
cout << "These are the Possible Permutations: " << endl;
int repeat = Factorial(n-k);
do
{
for (int i = 0; i < k; i++)
{
cout << d[i] << " ";
}
cout << endl;
for (int i=1; i!=repeat; ++i)
{
next_permutation(d.begin(),d.end());
}
} while (next_permutation(d.begin(),d.end()));
}
However, there is an even easier and more efficient way to do it using std::reverse (from https://stackoverflow.com/a/2616837/951890)
void PermGenerator(int n, int k)
{
std::vector<int> d(n);
std::iota(d.begin(),d.end(),1);
cout << "These are the Possible Permutations: " << endl;
do
{
for (int i = 0; i < k; i++)
{
cout << d[i] << " ";
}
cout << endl;
std::reverse(d.begin()+k,d.end());
} while (next_permutation(d.begin(),d.end()));
}
The trick here is to realize that the last permutation is just the reverse of the first permutation, so by reversing the last n-k elements, you automatically skip to the last permutation of those elements.
Creating a power set of a Sequence
Power set is easy to generate if one is familiar with bits. For the set of N
elements, there will be 2^N
subsets which will go to power set (including empty set and initial set). So each element will be either IN or OUT (1
or 0
in other words).
Taking this into consideration, it is easy to represent subsets of the set as bit masks. Then enumerating through all possible bit masks, it is possible construct the whole power sets. In order to do this we need to examine each bit in bit mask and take element of input set if there is 1
in that place. Below is example for string
(collection of chars) as input. It can be easily rewritten to work for collection of any type values.
private static List<string> PowerSet(string input)
{
int n = input.Length;
// Power set contains 2^N subsets.
int powerSetCount = 1 << n;
var ans = new List<string>();
for (int setMask = 0; setMask < powerSetCount; setMask++)
{
var s = new StringBuilder();
for (int i = 0; i < n; i++)
{
// Checking whether i'th element of input collection should go to the current subset.
if ((setMask & (1 << i)) > 0)
{
s.Append(input[i]);
}
}
ans.Add(s.ToString());
}
return ans;
}
Example
Suppose you have string "xyz"
as input, it contains 3 elements, than there will be 2^3 == 8
elements in power set. If you will be iterating from 0
to 7
you will get the following table. Columns: (10-base integer; bits representation (2-base); subset of initial set).
0 000 ...
1 001 ..z
2 010 .y.
3 011 .yz
4 100 x..
5 101 x.z
6 110 xy.
7 111 xyz
You can notice that third column contains all subsets of initial string "xyz"
Another approach (twice faster) and generic implementation
Inspired by Eric's idea, I have implemented another variant of this algorithm (without bits now). Also I made it generic. I believe this code is near to fastest of what can be written for Power Set calculation. Its complexity is the same as for bits approach O(n * 2^n)
, but for this approach constant is halved.
public static T[][] FastPowerSet<T>(T[] seq)
{
var powerSet = new T[1 << seq.Length][];
powerSet[0] = new T[0]; // starting only with empty set
for (int i = 0; i < seq.Length; i++)
{
var cur = seq[i];
int count = 1 << i; // doubling list each time
for (int j = 0; j < count; j++)
{
var source = powerSet[j];
var destination = powerSet[count + j] = new T[source.Length + 1];
for (int q = 0; q < source.Length; q++)
destination[q] = source[q];
destination[source.Length] = cur;
}
}
return powerSet;
}
All Possible Combinations of a list of Values
try this:
static void Main(string[] args)
{
GetCombination(new List<int> { 1, 2, 3 });
}
static void GetCombination(List<int> list)
{
double count = Math.Pow(2, list.Count);
for (int i = 1; i <= count - 1; i++)
{
string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
for (int j = 0; j < str.Length; j++)
{
if (str[j] == '1')
{
Console.Write(list[j]);
}
}
Console.WriteLine();
}
}
Related Topics
Where Should Non-Member Operator Overloads Be Placed
Why am I Able to Make a Function Call Using an Invalid Class Pointer
C++ - Std::Thread Crashes Upon Execution
Passing Constexpr Objects Around
C++ Circular Dependency in Header Files
How to Get Size C++ Dynamic Array
C++ Double Dispatch for Equals()
Convert Integer to Binary and Store It in an Integer Array of Specified Size:C++
Ptr->Hello(); /* Versus */ (*Ptr).Hello();
Possible Memory Leak Without a Virtual Destructor
Recursion in C++ Factorial Program
How Serious Is the New/Delete Operator Mismatch Error
What Is the Use of "Using Namespace Std"
Pass Arrays from C/C++ to Fortran and Return a Calculated Array