2

I have been hitting my head against an algorithmic problem for a couple of hours now.

The (fancy) statement of the problem is as follows:

Our garden contains a single row of flowers.You are given the current contents of the row in the String garden. Each character in garden represents one flower. Different characters represent different colors.Flowers of the same color all look the same. You may rearrange the flowers in your garden into any order you like. (Formally, you may swap any two flowers in your garden, and you can do so arbitrarily many times.) You are also given a String forbid of the same length as garden.You want to rearrange garden into a new string G that will satisfy the following conditions :

No two adjacent flowers will have the same color.Formally, for each valid i, G[i] and G[i + 1] must differ. For each valid i, G[i] must not be equal to forbid[i]. Let X be the number of different strings G that satisfy all conditions given above.Compute and return the number(X modulo 1, 000, 000, 007).

Just to clarify with an example: X("aaabbb", "cccccc") = 2 ("ababab" and "bababa")

I have been trying by counting how many letters are in the string ( 'a'->3, 'b'->4, in the example) and then recursively counting the different possibilities (skipping if there is a repetition or a forbidden letter). Something on these lines:

using Map = std::map < char, size_t > ;
Map hist; 
std::string forbid;

size_t countRecursive(std::string s, size_t len)
{
    if (len == 0)
        return 1;

    size_t curPos = s.size() ;
    size_t count(0);

    for (auto &p : hist) {
        auto key = p.first;

        if (hist[key] == 0) continue;
        if (forbid[curPos] == key) continue;
        if (curPos > 0 && s[curPos - 1] == key) continue;

        hist[key]--;            
        count += countRecursive(s + key, len - 1);
        hist[key]++;
    }


    return count;
}

Where hist and forbid are previously initialized. However, this appears to be n! and since n can be <= 15, it really explodes in complexity.

I am not really looking for a complete solution. Only, if you had any kind of suggestion about the way I should approach the problem, I would be highly thankful!

  • Are you trying to *count* the number of such arrangements or are you trying to *generate* them? The former is easier. – John Coleman Apr 30 '16 at 20:23
  • I am trying just to count, but still I am not able to think about a good (performance-wise) solution :/ – Giuseppe Rossini Apr 30 '16 at 20:57
  • http://stackoverflow.com/questions/25285792/generate-all-permutations-of-a-list-without-adjacent-equal-elements/32366585#32366585 – m69's been on strike for years Apr 30 '16 at 22:38
  • @m69 I am not fully convinced this is the right answer. Let's say I have "abcdefghijklmno" (15 letters) and that the forbid string is all "z"s. I will have 15! combinations and the algorithm mentioned in the link (as far as I understood) will go through all of them – Giuseppe Rossini Apr 30 '16 at 22:51
  • Your problem indeed has the extra condition of the forbid list. You can use ideas from the question in the link to get the total number of permutations, and then you need to find the number of forbidden permutations and subtract them. – m69's been on strike for years Apr 30 '16 at 23:42

1 Answers1

0

I'd approach it as follows: your 'forbidden' string is as long as the 'garden'. This means that given an alphabet of N characters, each position G[i] can have at most N-1 possible characters (since one will be forbidden). This gives you an upper bound that's limited only by N. If that bound is less than the modulo it might lead to some interesting considerations, but let's move forward.

Now a very basic approach is counting the combinations: if the garden is K characters long, the first item G[0] will have N-1 possibilities; the second one G[1] will have N-2 possibilities if forbidden[1] is different than G[0], N-1 if forbidden[1] == G[0]. The third character G[2] will too have N-2 possibilities depending on forbidden[2] and G[1], and so on.

For clarity: N-2 comes from the fact that of the N-1 possibilities, another one must be removed that is the value of the character preceding it in the string, unless such character matches the forbidden character of the current position.

So if forbidden[i+1] is always different from G[i] you have N-1 * N-2 * N-2 * ... * N-2, K times. This is your lower bound.

Now between upper and lower bound there is a number of strings where e.g. forbidden[i+1] is equal to G[i] only for the second position; for the second and for the third; etc. So your number of strings is:

N-1 * N-2 * N-2 * N-2 ... K
N-1 * N-1 * N-2 * N-2 ... K
N-1 * N-1 * N-1 * N-2 ... K

and so on until you have a string where each character can have N-1 possibilities.

In other words,

N-1 * (N-2)^K-1
(N-1)^2 * (N-2)^K-2
(N-1)^3 * (N-2)^K-3

How many of those strings can you have? It depends how big is K, i.e. how large is your garden :)

That is, assuming I understood the problem correctly.

lorenzog
  • 3,483
  • 4
  • 29
  • 50
  • If I understood it correctly, you are assuming that forbid contains characters in the alphabet, but this is not always the case. In the example I gave, G = "aaabbb" and forbid = "cccccc". – Giuseppe Rossini Apr 30 '16 at 23:18
  • And also, I cannot insert unlimited letters for my alphabet. For instance, in the same example, the alphabet is "ab", but I can dispose of 3 "a"s and 3 "b"s – Giuseppe Rossini Apr 30 '16 at 23:36
  • @GiuseppeRossini then how can you verify that `For each valid i, G[i] must not be equal to forbid[i]`? Also, the limited number of letters further reduces the possibilities (think of it as combinations without repetition) – lorenzog May 01 '16 at 10:12