-1

Recently I came across an algorithmic problem which asks to generate the unique subsets from a given set. Suppose when the set is S={1, 2, 3, 4} where n=4 (number of elements). then the result should generate all n*(n-1)/2 subsets:- {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

#include<iostream>
int main()
{
int k;
std::cin>>k;
for(long int i=1;i<=k;i++)
{
    for(long int j=i+1;j<=k;j++)
    {
        std::cout<<i<<" "<<j<<"\n";
    }
}
return 0;
}

I have an O(n^2) approach but the problem that arising is when the numbers are large for n=1000 it takes lot of time since it had to generate 499,500 elements!

Does anyone has a Better solution complexity wise? algorithm would be appreciated!

kmkaplan
  • 18,655
  • 4
  • 51
  • 65
Amireddy Tharun reddy
  • 21
  • 8
  • 5
    By "subsets", do you mean just "pairs of unique elements"? This is fundamentally a n^2 problem, you won't find an algorithm that can do it any faster. – Alexander Apr 14 '17 at 15:46
  • Yes i meant that . Is that so ? :-( – Amireddy Tharun reddy Apr 14 '17 at 15:50
  • You could only do better if you didn't have to generate all pairs, and could order the generation better. – jwimberley Apr 14 '17 at 15:52
  • See http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n. This question is probably a duplicate of that. – Jim Mischel Apr 14 '17 at 15:56
  • 1
    @AmireddyTharunreddy You said it yourself: your algorithm needs to do the work to generate 499,500 pairs of unique elements in a set of 1000 elements. Nothing your algorithm could do can change that. – Alexander Apr 14 '17 at 15:58
  • C++ cannot break the rules of computer science. If there is no algorithm with the desired complexity, then C++ cannot magically act as if there was one. If you don't *know* whether there is such an algorithm, then corresponding questions and answers won't have anything to do with C++, because the problem statement would be identical in various different programming languages. – Christian Hackl Apr 14 '17 at 16:02
  • The C++ language tag is only appropriate if you *know* that there is such an algorithm but are struggling with its implementation in C++. – Christian Hackl Apr 14 '17 at 16:03
  • Sorry ,I assumed that an efficient solution existed. – Amireddy Tharun reddy Apr 14 '17 at 16:07
  • @AmireddyTharunreddy When you think about it more conceptually, you say you need to generate all n*(n-1)/2 pairs. Imagine you want to print each one of those pairs. We can estimate the printing of one pair if Ω(1). Then, since you need to print all n*(n-1)/2 pairs, you have Ω(n*(n-1)/2) = Ω(n^2). There is no way around it, since the problem asks you specifically to print all n*(n-1)/2 of them. The printing itself will get you to Ω(n^2). Note, we are talking about a lower bound here (Ω) - this is the amount of steps you have to take *at least*. You can surely come up with a slower algorithm. – Michał Apr 14 '17 at 16:26
  • @Michał thanks ! That was helpful ! :-) – Amireddy Tharun reddy Apr 14 '17 at 16:38
  • Define "efficient". If you're generating n^2 unique items, how can we have an algorithm with faster runtime than that? – Donnie Apr 14 '17 at 20:25

1 Answers1

0

The number of subsets of a set of size n is 2^n. Here, probably only subsets of size 2 are asked. Hence, the number of such subsets is n*(n-1)/2.

Since each of those sets are unique, to generate them, at least those many computations are required.

Hence, the minimum complexity is bounded by these numbers Ω(n^2) and Ω(2^n) for these cases.

Kalyan Raghu
  • 1,005
  • 1
  • 10
  • 19