0
\$\begingroup\$

I would like to return or save for later use in the ParallelSums function what I currently have printing out to the console in the findAllSubsetsRec function.

If I pass the ParallelSums function an int array of [16, 22, 35, 8, 20, 1, 21, 11] I currently get the console output from the findAllSubsetsRec of:

22 20 16 8 1
22 21 16 8
35 20 11 1
35 21 11

I would like each line that is seen above to be returned to my ParallelSums function, probably in multiple lists or in a way that I can later put them in multiple lists/arrays, so that I can do some further processing on them.

Below is the code I have so far:

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

class MainClass {
  static void findAllSubsetsRec(int []arr, int n, List<int> v, int target) {
     List<int> subList = new List<int>();
    // if the remaining target is 0, add elements to subList
    if(target == 0) {
      for (int i=0; i<v.Count; i++) {
        Console.Write(v[i]+ " ");
        subList.Add(v[i]);
      }
      Console.WriteLine();
      return;
    }
    // if there are no elements remaining return
    if (n == 0) {
      return;
    }
    // two cases to consider for every element
    // 1. we won't include the last element
    // 2. we will include the last element in current subset
    findAllSubsetsRec(arr, n-1, v, target);
    List<int> v1 = new List<int>(v);
    v1.Add(arr[n-1]);
    findAllSubsetsRec(arr, n-1, v1, target-arr[n-1]);
  }

  public static int ParallelSums(int[] arr) {
    // variable initialization

    // manually set number of sub arrays we are looking to use
    // so we can write code to work for anything and then restrict
    // it to work for this particular case
    int numOfSubArr = 2;

    // determine if we have enough elements in arr to allow for
    // an even number of elements for each sub array per requirements
    int evenNumElementsPerArr = arr.Length%numOfSubArr;

    // find our target number for our sub arrays to equal
    int arrSum = arr.Sum();
    int target = arr.Sum()/numOfSubArr;
    int possibleTarget = arrSum%numOfSubArr;
    Console.WriteLine("possibleTarget = " + possibleTarget);
    Console.WriteLine("Target Number = {0}", target);
    Console.WriteLine("Possible target for equal length sub arrays? " + ((possibleTarget==0)?"yes":"no"));
    Console.WriteLine("Even number of elements per array? " + ((evenNumElementsPerArr==0)?"yes":"no"));
    // validation checks
    if (evenNumElementsPerArr != 0 || possibleTarget != 0) {
      Console.WriteLine("Array of odd numbered length or can't be equally divided into sub arrays"); 
      return -1;
    } else {
        Console.WriteLine("We have an even number of elements and sub array lengths");
      
        // initialize arrays and variables for sums
        int n = arr.Length;
        List<int> v = new List<int>();

        // sort our input array
        Array.Sort(arr);

        findAllSubsetsRec(arr, n, v, target);
    }
    // will eventually return my desired results, but for now will just return 1
    return 1;
  }

  static void Main() {  
    // keep this function call here
    Console.WriteLine(ParallelSums(Console.ReadLine()));
  } 

}

The end goal is to take all of these lists and determine which 2 contain all the numbers from the input array, without using any twice, while both lists have an equal length/count of elements.

In my example below the list of [22,21,16,8] and [35,20,11,1] would ultimately be the two correct lists to solve my problem.

Any help would be very much appreciated and I'm open to changing my methodology if something else makes more sense than what I'm doing now.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Only working as intended code is suitable for Code Review. You may ask the question on StackOverflow instead. \$\endgroup\$
    – aepot
    Jun 20 '21 at 8:28
  • 1
    \$\begingroup\$ Welcome to Code Review. I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Heslacher
    Jun 21 '21 at 4:32
0
\$\begingroup\$

I added a private static Dictionary<int, List<List<int>>> _dictionary = new Dictionary<int, List<List<int>>>(); so that I can access the dictionary at any level of the recursion and then enter values like this:

if (!_dictionary.ContainsKey(v.Count))
{
    _dictionary.Add(v.Count, new List<List<int>>());
}

_dictionary[v.Count].Add(v);

You can then see which entries you actually care about by using only the ones that are exactly half of the input array. From there, you can do any other processing you might need.

One other thing I would ask is how you are planning to handle duplicates in the original array? It should be simple enough to keep track by removing the values as you compare and then resetting if the arrays don't meet your criteria but, if not handled properly, could flag a failed case accidentally if not handled.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thank you for your input Trevor. I hadn't fully considered duplicates in my original array input, but figured I'd get some output first and then see what I needed to do to clean up those cases. I'll give your dictionary a go and follow up once I have more. \$\endgroup\$
    – Max Varner
    Jun 20 '21 at 1:57
  • \$\begingroup\$ @MaxVarner I can't comment on your update but the reason your output looks the way it does is you aren't printing correctly. You are printing all lists with a certain key on one line instead of breaking them up by line. You can fix this in one of two ways: either move your Console.Write("\n" + i.Key + ":"); statement in one foreach loop OR add a Console.WriteLine() before the innermost foreach so each line is on its own line. \$\endgroup\$
    – Trevor
    Jun 20 '21 at 14:08
  • \$\begingroup\$ Ahh yes! I see. I've made the changed of moving my Console.Write("\n" + i.Key + ":"); to the second foreach loop and now I have the output as expected. I was thinking that I needed unique keys for each item in the dictionary to be able to access them later individually, but I can, and probably should, just transition those lists out of the dictionary to do my additional logic for determining the correct ones to ultimately output. I haven't used dictionaries before so I'm not fully familiar with all the things they can do at this time. Thank you again Trevor! \$\endgroup\$
    – Max Varner
    Jun 20 '21 at 19:50
  • 1
    \$\begingroup\$ Limiting the output in the dictionary from findAllSubsetsRec() to only add the items to a temp list that had a key value equal to half of my original array length; I was able to see that the first key value number of items in the temp list and the last key value number of items in the list seemed to always be a matching subset that contained all of the values in the original array while not duplicating any across each subset. This seemed to hold true even if I had duplicate numbers in my original array. This pattern continued as you moved to the second and second to last subset and so on. \$\endgroup\$
    – Max Varner
    Jun 23 '21 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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