CODEWITHSUNDEEP
algorithmpermutationcombinationsapriori
coolharsh55
coolharsh55

Reputation: 1199

how to generate the following sequence?

I want to generate the following sequence:

set S = {1,2,3}
op = {{1,2},{1,3},{2,3}}

set S = {1,2,3,4}
op = {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

set S = {1,2,3,4,5}
op = {{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}

in general, given a set of n numbers, I have to find all the possible subsets of (n-1) numbers with the constraint that they are in alphabetical order (numbers in order).

Is there any algorithm or approach to solve the particular problem? I know that we can use recursion to generate smaller subsets.

Upvotes: 1

Views: 135

Answers (5)

Déjà vu
Déjà vu

Reputation: 28840

Think about

  • how to generate the set 1..N
  • how to identify the number n to be removed from each set (n: N .. 1)

To generate/print a set from 1..N

print "{"
for i=1 to N
  if (i > 1) print ","
  print i
end
print "}"

How to create a loop that selects n from N to 1

for j=N to 1 
  ...
end

Use that last loop as a wrapper around that above loop - and in the above loop test if the current selected number j is equal to i and don't print it in that case.

For the fun a Perl implementation that does not pretend to be optimized :-)

$N = 5;

sub rec {
  my($j,$i,@a) = @_;
  if ($j > 0) {
    while (++$i <= $N) { push(@a,$i) if ($i != $j); }
    print('{' . join(',', @a) . "}\n");
    &rec($j-1);
  }
}

&rec($N);

Or this, (maybe) more conventional

for ($i=$N ; $i>0 ; $i--) {
  @a = ();
  for (1..$N) { push(@a,$_) if ($i != $_); }
  print('{' . join(',', @a) . "}\n");
}

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

In Haskell you could do this:

import Data.List

combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

subsets set =  combinations (length set - 1) (sort set)


Haskell, briefly:

_                                   =>    anyting
[]                                  =>    empty list
a = 1; as = [2,3]                   =>    a:as = [1,2,3]
[a:b | a <- [1], b <- [[2],[3]]]    =>    [[1,2],[1,3]]
tails [1,2,3]                       =>    [[1,2,3],[2,3],[3],[]]


For example, "combinations 2 [1,2,3]":

tails xs = [[1,2,3],[2,3],[3],[]]

[1,2,3]   =>   y = 1; ys = [[2],[3]]    =>    [1,2],[1,3]
[2,3]     =>   y = 2; ys = [[3]]        =>    [2,3]
[3]       =>   y = 3; ys = NULL         =>    []

Result [[1,2],[1,3],[2,3]]

Upvotes: 1

user1952500
user1952500

Reputation: 6771

This should be simple enough. Let arr have the sorted set and n be the number of elements:

int arr[100];
int n;
printf("{");
for (int i = n - 1; i >= 0; i--){
    printf("{");
    for (int j = 0; j < n; j++) {
        if (i == j) {
            continue;
        }
        printf("%d, ", arr[j]);
    }
    printf("}, ");
}
printf("}\n");

The above prints some additional commas and you can filter them out yourself.

Upvotes: 2

acattle
acattle

Reputation: 3113

Some languages have this functionality built-in. For example, Python's itertools.combinations() method. In your case:

>>> import itertools
>>> l = [1,2,3,4]
>>> combinations = itertools.combinations(l, len(l) -  1) #for the list of numbers l, for sublists with a length 1 less than l's length
>>> for comb in combinations:
...     print comb
...
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)
>>>

However, if you want to implement this yourself the link above may still prove useful as it shows equivalent code. You could use this code to make your own implementation in any language.

Upvotes: 2

Andrew Mao
Andrew Mao

Reputation: 36900

There are only n such subsets; each one with one of the n original numbers removed from the original set. So sort the set, and for each of the numbers, create a set which is the original set with that number removed.

A possible caveat is that if there are duplicate numbers in the original set, you will only have as many subsets as there are unique numbers in the original set, so possibly fewer than n in that case.

Upvotes: 2

Related Questions