Computing Powersets in C#

Question

I tried to convert the below Java code into C#. The Java code works fine but C# code is not returning the powersets. Am I missing something?

Java Code

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    List<List<Integer>> subsets = new ArrayList<>();

    System.out.println(generateSubsets(
      0, 
      list.stream().mapToInt(i -> i).toArray(), 
      new ArrayList<Integer>(), 
      subsets));
}

static List<List<Integer>> generateSubsets(
    int index, 
    int[] nums, 
    List<Integer> current, 
    List<List<Integer>> subsets){
    
    subsets.add(new ArrayList<>(current));
    
    for(int i = index; i < nums.length; i++){
        current.add(nums[i]);
        generateSubsets(i + 1, nums,current, subsets);
        current.remove(current.size() - 1);
    }

    return subsets;
}

C# Code

static List<List<Integer>> generateSubsets(
    int index, 
    int[] nums, 
    List<Integer> current, 
    List<List<Integer>> subsets) {
    
    subsets.add(new List(current));

    for (int i = index; (i < nums.length); i++) {
        current.add(nums[i]);
        generateSubsets((i + 1), nums, current, subsets);
        current.remove((current.size() - 1));
    }
    
    return subsets;
}

Expected Output

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

*"Am I missing something?"* Input sample with expected output. Something reproducible — Cid, Dec 31 '20 at 15:27
I don't know Java well enough to know the properties on the List object, but based on what your code looks like it is trying to do, I'd say you need to change in the C# current.size() to current.Count. — Russ, Dec 31 '20 at 15:46

Dmitry Bychenko · Accepted Answer · 2020-12-31T16:26:55.083

It's seems it'll be easier to create generateSubsets from scratch then convert the routine from Java. We can implement the method with a help of Linq:

using System.Linq;

...

private static List<List<T>> generateSubsets<T>(List<T> source) {
  return Enumerable
    .Range(0, 1 << source.Count)
    .Select(index => Enumerable
      .Range(0, source.Count)
      .Where(i => (index & (1 << i)) != 0)
      .Select(i => source[i])
      .ToList())
    .ToList(); 
}

The idea which is behind the code is to generate all masks [0 .. 2**Count) and then take subset items according each mask:

000....000 - empty set (no items)
000....001 - set with 1st item only
000....010 - set with 2nd item only
000....011 - set with 1st and 2nd items
000....100 - set with 3d item only
..........
111....110 - set with all items except 1st one
111....111 - set with all items

Demo:

public static void Main(String[] args) {
  List<int> list = new List<int>() {
    1, 2, 3,
  };

  var subsets = generateSubsets(list); 

  Console.Write(string.Join(Environment.NewLine, subsets
    .Select(s => $"[{string.Join(", ", s)}]")));

  Console.ReadLine();
}

Outcome:

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

Computing Powersets in C#

1 Answers1

Linked