CODEWITHSUNDEEP
c#algorithm
Zoidfarb
Zoidfarb

Reputation: 61

Algorithm for generating all combinations with 2 potential values in 5 variables

Apologies if this has been answered before but I can't come up with a good name to search for what I'm looking for. I have the potential for between 1-5 string variables (we'll call them A,B,C,D,E) that can have one of two values represented by 'P' and 'S'. These are for pluralized and singular word forms

The data will always be in the same order, ABCDE, so that is not a concern but it may not contain all five (could be only A, AB, ABC or ABCD). I'm looking for an algorithm that will handle that possibility while generating all potential plural/singular combinations. So in the case of a 5 variable string the results would be: SSSSS, SPSSS, SPPSS, SPSPS, ... PPPPP

I have the logic to pluralize and to store the data it's just a question of what is the logic that will generate all those combinations. If it matters, I am working in C#. Any help would be greatly appreciated!

Upvotes: 2

Views: 914

Answers (4)

Balah
Balah

Reputation: 2540

"Recursive permutations C#" will do the trick for a google search. But I thought I'd attempt a solution for you using simple counting and bit masking. Here is some code that will do "binary" counting and, using bitshifting, determine if the position in the words should be pluralized (you mention you have those details already):

string input = "red bag";
string[] tokens = input.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

string[] test = new string[tokens.Length];

int size = (int)Math.Pow(tokens.Length, 2);

for (int i = 0; i < size; i++)
{
    for (int j = 0; j < tokens.Length; j++)
    {
        int mask = (1 << j);
        if ((mask & i) != 0)
        {
            test[j] = Pluralize(tokens[j]);
        }
        else
        {
            test[j] = Singularize(tokens[j]);
        }
    }

    Console.WriteLine(string.Join(" ", test));
}

Output:

red bag
reds bag
red bags
reds bags

Upvotes: 0

Igor Bendrup
Igor Bendrup

Reputation: 2837

You can enumerate all integers from 0 to 2^5-1 (i.e. from 0 to 31 ) and represent each integer as bool[]. May be this will be helpful:

static bool[][] GetCombinations(int wordCount) {
    int length = (int) Math.Pow(2, wordCount);
    bool[][] res = new bool[length][];
    for (int i = 0; i < length; i++)
    {
        res [i] = new bool[wordCount];
        for (int j = 0; j < wordCount; j++) {
            res [i] [j] = ((i & (int)Math.Pow (2, j)) != 0);
        }
    }
    return res;
}

Upvotes: 0

timschoen
timschoen

Reputation: 171

I would advise a recursive algorithm. For example an algorithm like this could be the answer to your problem (I dont really know what returnvalues you exactly want)

public void getAllWords(ref List<string> result, string Prefix, int wordLength)
{
  if(wordLength == 0)
    result.add(prefix);
  else
  {
    getAllWords(result, prefix+"0", wordLength-1);
    getAllWords(result, prefix+"1", wordLength-1);
  }
}

to be called with

List<string> result = new List<string>();
getAllWords(result, "", 5);

I hope this works, I'm on mobile at the moment.

You can change that as you want to account for m a different alphabet (for example values 0,1,2..) as you like.

Upvotes: 0

BambooleanLogic
BambooleanLogic

Reputation: 8161

So there are only two possible values, 0 and 1. Wait a minute... Zeroes and ones... Why does that sound familiar...? Ah, binary to the rescue!

Let's count a little in binary, starting with 0.

  • 0000 = 0
  • 0001 = 1
  • 0010 = 2
  • 0011 = 3
  • 0100 = 4
  • 0101 = 5
  • 0110 = 6
  • 0111 = 7
  • 1000 = 8
  • ...etc

If you look at the rightmost bit of the first two rows, we have all the possible combinations for 1 bit, 0 and 1.

If you then look at the two rightmost bits of the first four rows, you get all 2 bit combinations: 00, 01, 10 and 11.

The first eight rows have all three bit combinations, etc.

If you want all possible combinations of x bits, count all numbers from 0 to (2^x)-1 and look at the last x bits of the numbers written in binary.

(Likewise, if you instead have three possible values (0, 1 and 2), you can count between 0 and (3^x)-1 and look at the last x digits when written in ternary, and so on for all possible amounts of values.)

Upvotes: 2

Related Questions