Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have a task to print all zero subsets of 5 numbers, input from the console. I have succeeded in implementing a working code, but it seems it is quite complex (it is like inception) and if the count of the numbers is to be greater, it would be rather pointless to use such a method.

using System;
using System.Collections.Generic;
using System.Linq;

class ZeroSubset
{
    static void Main()
    {
        int number;
        int[] Numbers = new int[5];
        bool result = false;
        for (int i = 0;i <=4; i++)
        {
            here: ;
            Console.WriteLine("Input number {0}", i + 1);
            if (int.TryParse(Console.ReadLine(), out number))
            {
                Numbers[i] = number;
            }
            else
            {
                goto here;
            }
        }

        if (Numbers[0] == 0 && Numbers[1] == 0 && Numbers[2] == 0 && Numbers[3] == 0 && Numbers[4] == 0)
        {
            result = true;
            Console.WriteLine(String.Join("+", Numbers) + " = 0");
            return;
        }

        for (int firstNum = 0; firstNum <= 3; firstNum++)
        {
            for (int secondNum = firstNum + 1; secondNum <= 4; secondNum++)
            {
                if (Numbers[firstNum] + Numbers[secondNum] == 0)
                {
                    result = true;
                    Console.WriteLine("{0} + {1} = 0", Numbers[firstNum], Numbers[secondNum]);
                }
            }
        }

         for (int firstNum = 0; firstNum <= 2; firstNum++)
         {
            for (int secondNum = firstNum + 1; secondNum <= 3; secondNum++)
            {
                for (int thirdNum = secondNum + 1; thirdNum <= 4; thirdNum++)
                {
                    if (Numbers[firstNum] + Numbers[secondNum] + Numbers[thirdNum]== 0)
                    {
                        result = true;
                        Console.WriteLine("{0} + {1} + {2} = 0", Numbers[firstNum], Numbers[secondNum], Numbers[thirdNum]);
                    }
                }
            }
        }

        for (int firstNum = 0; firstNum <= 1; firstNum++)
        {
            for (int secondNum = firstNum + 1; secondNum <= 2; secondNum++)
            {
                for (int thirdNum = secondNum + 1; thirdNum <= 3; thirdNum++)
                {
                    for (int fourthNum = thirdNum + 1; fourthNum <= 4; fourthNum++)
                    {
                        if (Numbers[firstNum] + Numbers[secondNum] + Numbers[thirdNum] + Numbers[fourthNum]== 0)
                        {
                            result = true;
                            Console.WriteLine("{0} + {1} + {2} + {3} = 0", Numbers[firstNum], Numbers[secondNum]
                                    , Numbers[thirdNum], Numbers[fourthNum]);
                        }
                    }
                }
            }
        }

        if (Numbers.Sum() == 0)
        {
            result = true;
            Console.WriteLine(String.Join("+", Numbers) + " = 0");
        }

        if (result == false)
        {
            Console.WriteLine("no zero subsets");
        }
    }
}

I am asking for a more simple approach to this matter.

share|improve this question
    
The zero subset sum problem algorithms are briefly described here. Just implement one of them... –  Patryk Ćwiek Apr 18 at 11:24
    
Does it have to be an array? I mean, is using LINQ cheating? if (numbers.All(n => n == 0)) { result = true; /* ... */ } –  Mat's Mug Apr 18 at 12:27
    
Your solution does not handle empty set and 1 element subsets. –  abuzittin gillifirca Apr 24 at 12:36
add comment

4 Answers 4

up vote 6 down vote accepted

As soon as I see a goto I get nostalgia, and know that you haven't taken a step back from this program and considered a world without goto (java). There is always a way to avoid using a goto, and this is a rather simple one with multiple alternatives which don't kill your program flow.

I think the best one for your situation though is to only increment up when the TryParse is successful.

for (int i = 0; i < Numbers.Length;)
{
    Console.WriteLine("Input number {0}", i + 1);
    if (int.TryParse(Console.ReadLine(), out number))
        Numbers[i++] = number;
}

EDIT: Changed to add additional alternative that does not include i in the fail-success of the parse logic.

for (int i = 0; i < Numbers.Length; i++)
{
    for(bool done = false; !done;)
    {
        Console.WriteLine("Input number {0}", i + 1);
        done = int.TryParse(Console.ReadLine(), out number);
    }
    Numbers[i] = number;
}

Note: I used < Numbers.Length, this way if you ever increase the size of the array, you can support more numbers without having to re-write this part.


Next we can simplify some of your code with linq, which you should use any time you want to repeatedly do something to a list. Below, using linq, I query the list of numbers and I ask if all of them equal 0.

if (Numbers.All(n => n == 0))
{
    Console.WriteLine(String.Join("+", Numbers) + " = 0");
    return;
}

Also note that I removed you setting result = true, because you were not using that since your were returning right away.


Naming convention: All of your method level variables should start with a lowercase letter, be camelCase, ie. numbers vs Numbers


Your program is a bit flawed. Technically just 0 is a subset of {0,1,2,3,4} however you appear to only care of subsets of 2 or more numbers.


A good alternative to your current implementaiton would have been to create a recursive function which takes in int[] remainingNumbers, int[] currentComposite, and the method would simply loop over the remainingNumbers and making new composites to check on, each time you would want to check just the currentComposite to see if that is a valid set.

The way I would do it, would be to create a list of number arrays which hold every combination of the given numbers, then I would simply loop over that collection to determine which sets fit my conditions.

Here is some code I found online (specifically here), because I did not want to make my own Combination generator. I'm going to post this code on CR, because I'd like to see someone take a stab at making it better.

static List<List<int>> Combinations(int[] array, int startingIndex = 0, int combinationLenght = 2)
{
    List<List<int>> combinations = new List<List<int>>();
    if (combinationLenght == 2)
    {
        int combinationsListIndex = 0;
        for (int arrayIndex = startingIndex; arrayIndex < array.Length; arrayIndex++)
        {
            for (int i = arrayIndex + 1; i < array.Length; i++)
            {
                combinations.Add(new List<int>());

                combinations[combinationsListIndex].Add(array[arrayIndex]);
                while (combinations[combinationsListIndex].Count < combinationLenght)
                {
                    combinations[combinationsListIndex].Add(array[i]);
                }
                combinationsListIndex++;
            }
        }
        return combinations;
    }
    List<List<int>> combinationsofMore = new List<List<int>>();
    for (int i = startingIndex; i < array.Length - combinationLenght + 1; i++)
    {
        combinations = Combinations(array, i + 1, combinationLenght - 1);

        for (int index = 0; index < combinations.Count; index++)
            combinations[index].Insert(0, array[i]);

        for (int y = 0; y < combinations.Count; y++)
            combinationsofMore.Add(combinations[y]);
    }
    return combinationsofMore;
}

Now just use some linq to only grab results from the Combinations function where the sum of the numbers in the list equates to 0. Foreach of them, print it to the console.

foreach(var list in Combinations(Numbers).Where(list=> list.Sum() == 0))
    Console.WriteLine(string.Join(" + ", list) + " = 0");

I see that at the bottom of your code you are checking to see if all the values in Numbers are 0, and then printing a message, and returning. Why? You did this earlier, and had an early return, so if that was the case the code should never have made it here.

share|improve this answer
    
Let me nearly repeat the comment I gave to Vogel612's answer: Changing the loop variable (i) inside the loop makes the code harder to reason about. –  Nobody Apr 18 at 18:38
    
@Nobody thats what those values are for. otherwise I would have declared a value outside set it equal to 0 and counted up on ever success, oh wait.. that is exactly what the for-loop does. It would make less sense to decremented it to have it re-incremented. But both ideas work better than a goto.. and I like to think mine is the right way to do it :) –  BenVlodgi Apr 18 at 19:04
    
@Nobody: actually I just changed it to not include i in the success or fail of the parse. its longer but it doesn't confuse the logic, which some people may indeed like :) –  BenVlodgi Apr 18 at 19:11
add comment

Using a List<int> instead of int[] allows your code to not only be more dynamic but also to leverage the GetRange method of the List. This simplifies your code to only 2 loops.

Creating the list would look something like this:

int number;
List<int> Numbers = new List<int>();
for(int i = 0; i <= 4; i++)
{
    number = 0;
    bool good = false;
    while(!good)
    {
        Console.WriteLine("Input number {0}", i + 1);
        if(int.TryParse(Console.ReadLine(), out number))
        {
            Numbers.Add(number);
            good = true;
        }
        else
            Console.WriteLine("Invalid input, try again");
    }

}

The sub routine to get the subsets could look something like this:

public static List<List<int>> AllSubsets2(List<int> mainset, int targetsum)
{
    List<List<int>> outval = new List<List<int>>();
    for(int num2 = 0; num2 < mainset.Count; num2++)
    {
        if(mainset[num2] == 0)
            outval.Add(new List<int>{mainset[num2]});
        int sum = mainset[num2];
        for(int num = num2+1; num < mainset.Count; num++)
        {
            sum += mainset[num];
            if(sum == 0)
                outval.Add(mainset.GetRange(num2, num - num2));
        }
    }

    return outval;
}

This will return a list of all the subsets that add up to the target sum.

share|improve this answer
    
The variable name good is a bit generic (something like hasEnteredValidInteger would be more to the point). I like the usability improvement with the extra "Invalid input" message. However, it should also mention what a valid input looks like. –  Nobody Apr 18 at 18:40
add comment

Your input loop:

for(int i = 0; i <= 4; i++)

is overly complicated to understand for the task at hand. Usually you iterate differently:

for (int i = 0; i < Numbers.Length; i++)

here: ;
if(int.TryParse(Console.ReadLine(), out number))
    Numbers[i] = number;
else
    goto here;

Do not use goto. It is evil, as it breaks the flow of the program and is extremely unsafe.

Instead you should decrement the loop-variable:

if(int.TryParse(Console.ReadLine(), out number))
    Numbers[i] = number;
else
    i--;

Conditionals:

if(result == false)

That is overly complicated and one statement too much. Use this instead:

if(!result)

Naming:

Be consistent in naming. Local variables in C# are named with camelCase by convention. PascalCasing is reserved for public Methods and Properties. Numbers should be numbers.

share|improve this answer
3  
I feel using the else branch to decrement i is a hack (changing the loop variable inside the loop makes the code harder to reason about). The natural controlflow would be do undcontionally increment i in the for loop and make an extra do while loop that exits when a correct number has been entered. –  Nobody Apr 18 at 11:29
add comment

I have succeeded in implementing a working code, but it seems it is quite complex (it is like inception) and if the count of the numbers is to be greater, it would be rather pointless to use such a method.

This is called Zero One Infinity Rule.

Here, you enumerate all subsets of some N (=5) numbers. You do this by first enumerating 2-element subsets then 3-element subsets and so on. And you couldn't generalize this to arbitrary N. (Not handling Zero and One cases can impede seeing the Infinity cases.)

When you meet a situation like this, take a step back and reexamine the problem. First restate the problem with N identified clearly and the statement of the problem doesn't include the method used to solve it. (This is another reason why you should extract snippets of your code and give them names indicating what they do and not how they do.)

As I mentioned before what you try to do above can be stated as "enumerate all subsets of some N (=5) numbers". The way to generalize this to arbitrary N is to look at how would one "enumerate all subsets of some N numbers, given all subsets of some N-1 numbers" and go from there. It is easy to figure out, then, that the subsets of N numbers consist of the subsets of the first N-1 of those numbers and those subsets obtained by adding the Nth element to each of those subsets.

The problem with your decomposition was that from the get go (2 element subsets) you are using all N elements.

Powerset of an IEnumberable:

public static IEnumerable<IEnumerable<T>> PowerSet<T>(IEnumerable<T> elements)
{
    return elements.Aggregate(
        new []{new T[]{}} as IEnumerable<IEnumerable<T>>,
        (subsetsSoFar, element) => subsetsSoFar.Concat(
            subsetsSoFar.Select(subset => subset.Concat(new[]{element}))));
}

The example of powerset implementations I could find online are not lazy and most copy around lists a lot and so this, apart from being shorter and more readable, also should behave better for larger input, though I haven't tried.

The rest is similar to other answers, except that if the subsets having at least 2 elements is a requirement, it should be stated (in the problem description as well as solution).

var zeroSumSubsets = PowerSet(numbers)
                     .Where(subset => subset.Count() > 1)
                     .Where(subset => subset.Sum() == 0);

foreach(var subset in zeroSumSubsets)
    // Do whatever...
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.