Combination of unique elements without repetition

Question

Elements : a b c all combinations in such a way:
a
b
c
ab
ac
bc
abc

Formula to get total number of combinations of unique elements without repetition = 2^n - 1 (where n is the number of unique elements)
In our case top: 2^3 - 1 = 7

Another formula to get the combinations with specific length = n!/(r! * (n - r)!) (where n= nb of unique items and r=length)
Example for our the above case with r=2 : 3!/(2! * 1!) = 3 which is ab ac bc

Is there any algorithm or function that gets all of the 7 combinations? I searched a lot but all i can find is one that gets the combinations with specific length only.

UPDATE:
This is what I have so far but it only gets combination with specific length:

void recur(string arr[], string out, int i, int n, int k, bool &flag)
{
    flag = 1;
    // invalid input
    if (k > n)
        return;

    // base case: combination size is k
    if (k == 0) {
        flag = 0;
        cout << out << endl;
        return;
    }

    // start from next index till last index
    for (int j = i; j < n; j++)
    {
        recur(arr, out + " " + arr[j], j + 1, n, k - 1,flag);
    }
}

*can find is one that gets the combinations with specific length only.* -- So make the "specific length" a variable, and call the combination function N times, from 1 to N (N being the "specific length"). — PaulMcKenzie, Dec 24 '19 at 13:45
@asynts because it has to do with apriori algo and association rules. — normaluser, Dec 24 '19 at 13:51
What is your question, actually? I mean, obviously there is algorithm, you applied it when you wrote the combinations in the question. — hyde, Dec 24 '19 at 13:53
Please see [this answer](https://stackoverflow.com/questions/9430568/generating-combinations-in-c/9430993#9430993) — PaulMcKenzie, Dec 24 '19 at 14:04
@hyde that was my thinking too - see an implementation of the recursive solution below — Allan Cameron, Dec 24 '19 at 15:55

Aqeel Ahmad · Accepted Answer · 2019-12-26T08:11:10.140

2

The best algorithm I've ever find to resolve this problem is to use bitwise operator. You simply need to start counting in binary. 1's in binary number means that you have to show number.

e.g.

in case of string "abc"

number  , binary , string

1       , 001    , c

2       , 010    , b

3       , 011    , bc

4       , 100    , a

5       , 101    , ac

6       , 110    , ab

7       , 111    , abc

This is the best solution I've ever find. you can do it simply with loop. there will not be any memory issue.

here is the code

#include <iostream>
#include <string>
#include <math.h> 
#include<stdio.h>
#include <cmath>

using namespace std;

int main()
{

    string s("abcd");
    int condition = pow(2, s.size());
    for( int i = 1 ; i < condition ; i++){ 
        int temp = i;
        for(int j = 0 ; j < s.size() ; j++){
            if (temp & 1){    // this condition will always give you the most right bit of temp.
                cout << s[j];
            }
            temp = temp >> 1;  //this statement shifts temp to the right by 1 bit.
        }
        cout<<endl;
    }
    return 0;
}

edited Dec 26 '19 at 08:11

answered Dec 24 '19 at 14:24

Aqeel Ahmad

709
7
20

Thanks, though the other 2 answers are correct but this seems to be faster. Btw I have removed the temp var and made the if condition like this if (i & (1 << j)) – normaluser Dec 24 '19 at 15:56
2

`pow(2, s.size())` -- Do not use `pow` with integer bases and exponents if the result will be in the range of an integer. There is no need to introduce floating point functions to do this work. Also, there is a possibility that `pow` can give incorrect answers due to floating point issues. [See this](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os). In addition, you're calling `pow` every time the loop iterates, thus slowing the program down unnecessarily. – PaulMcKenzie Dec 24 '19 at 16:27
@PaulMcKenzie correct ! We can calculate it once to get the total nb of combinations and then use the result in the loop. – normaluser Dec 26 '19 at 07:25
is there anything else you guys want me to edit in the above code? – Aqeel Ahmad Dec 26 '19 at 08:05
@PaulMcKenzie is this considered O(n * 2^n) ? – normaluser Jan 15 '20 at 08:00
@normaluser yes this will be the time complexity. – Aqeel Ahmad Jan 15 '20 at 08:52
@AqeelAhmad but the recursive function below provides O(2^n). However I tested both functions and urs appears to be much faster. So how is this possible? – normaluser Jan 15 '20 at 09:01
@normaluser one of the major factor is space complexity. Recursive call make a lot of copies in its stack which slows down the processing. – Aqeel Ahmad Jan 15 '20 at 09:12
@normaluser one more thing, this algorithm can be optimised by managing the inner loop. its time complexity can fall to O(logn * 2^n). – Aqeel Ahmad Jan 15 '20 at 09:20
@AqeelAhmad can u please show how to optimize the inner loop; sorry too many questions but it's important to me. – normaluser Jan 15 '20 at 14:50
@normaluser you only need to add one more condition inside of inner loop. ' j < s.size() && temp != 0 ' – Aqeel Ahmad Jan 20 '20 at 07:28

score 1 · Answer 2 · answered Dec 24 '19 at 13:53

Do a simple exhaustive search.

#include <iostream>
#include <string>

using namespace std;

void exhaustiveSearch(const string& s, int i, string t = "")
{
    if (i == s.size())
        cout << t << endl;
    else
    {
        exhaustiveSearch(s, i + 1, t);
        exhaustiveSearch(s, i + 1, t + s[i]);
    }
}

int main()
{
    string s("abc");
    exhaustiveSearch(s, 0);
}

Complexity: O(2^n)

Allan Cameron · Answer 3 · 2019-12-24T15:46:53.663

Here's an answer using recursion, which will take any number of elements as strings:

#include <vector>
#include <string>
#include <iostream>

void make_combos(const std::string& start,
                const std::vector<std::string>& input,
                std::vector<std::string>& output)
{
  for(size_t i = 0; i < input.size(); ++i)
  {
    auto new_string = start + input[i];
    output.push_back(new_string);
    if (i + 1 == input.size()) break;
    std::vector<std::string> new_input(input.begin() + 1 + i, input.end());
    make_combos(new_string, new_input, output);
  }
}

Now you can do:

int main()
{
  std::string s {};
  std::vector<std::string> output {};
  std::vector<std::string> input {"a", "b", "c"};
  make_combos(s, input, output);

  for(auto i : output) std::cout << i << std::endl;
  std::cout << "There are " << output.size() 
            << " unique combinations for this input." << std::endl; 


  return 0;
}

This outputs:

a
ab
abc
ac
b
bc
c
There are 7 unique combinations for this input.

Combination of unique elements without repetition

3 Answers3