Calculating all possibilities for a string with optional parts

user_10434371 0
Viewed 118

I want to generate a list of all possible combinations of a string that contains optional parts. This is probably best explained with some examples:

  • A[B] → A and AB
  • A[B][C] → A, AB, AC and ABC
  • A[B[C]] → A, AB and ABC

I hope this sufficiently explains what I'm trying to do.

I could hack together my own little parser or "algorithm" for this, but I have a strong feeling that there's an existing (and easier) solution for this. Because I don't have any kind of CS education (yet), I have no idea what kind of algorithm I'm looking for or even just what search terms to use.

Is my hunch correct and is there actually an existing (well-documented) approach for this?

combinatorics algorithm string
4 Answers

I haven't read the article but it seems that this question have been studied. There's an article page 117: "Enumeration of Formal Languages" http://www.eatcs.org/images/bulletin/beatcs89.pdf

You may find more on this subject by searching with the good keywords like "enumerate language for DFA"

user_20499150

The algorithm could be like the following:

- Parse the string and make a rooted binary tree that on each node breaks on 
the new bracket exists or not.

- You can go through the root to the leaf of the tree.
  All paths from the root to leaves generate all combinations.

Also you can use a push-down automaton to parse the string for knowing where a bracket is opened and where it is closed. There are many implementations for the case that you can find.

user_37688710

Here's something in JavaScript, only tested for the three examples provided. Hopefully the (attempted) recurrence is clear from the code:

function f(string, index, combinations){
  if (index == string.length)
    return [combinations, index]
    
  if (string[index] == "["){
    let prefixes = []
    let [suffixes, nextIndex] = f(string, index + 1, [""])

    for (let combination of combinations)
      for (let suffix of suffixes)
        prefixes.push(combination + suffix)

    if (nextIndex == string.length)
      return [combinations.concat(prefixes), nextIndex]
    else
      return f(string, nextIndex, combinations.concat(prefixes))
    
  } else if (string[index] == "]"){
    return [combinations, index + 1]
    
  } else {
    for (let i=0; i<combinations.length; i++)
      combinations[i] += string[index]
    return f(string, index + 1, combinations)
  }
}

strings = [
  "A[B]",
  "A[B][C]",
  "A[B[C]]"
]

for (let string of strings)
  console.log(JSON.stringify(f(string, 0, [""])[0]))

user_20347870

The grammar you defined contains only 2 different entities: Terminals (a character) or an Optional part of the grammar.

In the Haskell code below, this is reflected by the definition of the discriminated union Grammar.

The first task is to convert a given concrete syntax (e.g. "A[B]") into a list of Grammar parts (each terminal or optional). In the code below, the function fromString does just that.

The interesting part, though is how to generate all possible strings for a given syntax. In the code below, the function generate does this, recursively.

  • For an empty grammar list (which is the end of the recursion), the output is a single empty string.

  • If a terminal symbol is found in the grammar list at a given position, the respective character is pasted in front of all variations, generated from the remainder of the grammar list.

  • If an optional part is found in the grammar list, the list of the remainder of the grammar list is yielded twice; once with the optional part prepended and once without.

For the non-functional people reading this, it should be pointed out that fmap is a function which maps a list to another list (element wise). The other function I used in the code below, non-haskellers might stumble over is concat, which turns a list of lists into a list.

data Grammar = Terminal Char | Optional [Grammar] deriving (Show,Eq)

fromString :: String -> [Grammar] -> ([Grammar],String)
fromString [] acc = (acc,"")
fromString ('[':cs) acc = 
    let (o,rest) = fromString cs [] in
        fromString rest (acc ++ [Optional o])
fromString (']':cs) acc = (acc,cs)
fromString (c:cs) acc = fromString cs (acc ++ [Terminal c])

generate :: [Grammar] -> [String]
generate [] = [""]
generate ((Terminal c) : parts) = fmap (\s -> c : s) $ generate parts
generate ((Optional gs) : parts) = tails ++ (concat . fmap prependOpts $ tails)
    where 
        tails = generate parts
        opts = generate gs
        prependOpts :: String -> [String]
        prependOpts tail = fmap (\o -> o ++ tail) $ opts

Putting it all together in the REPL (interactive shell), running fromString "A[B][C]" [], for example yields:
([Terminal 'A',Optional [Terminal 'B'],Optional [Terminal 'C']],"")

And if we run generate on the grammar list above (the first part of the tuple), we get all our strings:
generate (fst $ fromString "A[B][C]" [])
["A","AC","AB","ABC"]

user_22251040
Related