Question

(C++! I didn't know if I should mention it or not) (Keep the order if at all possible!)

Say I have, and I do, the string ABaC.

I have each character in that string in a vector called temp.

So I have temp[0] = A, temp[1] = B, temp[3] = a, temp[4] = C.

What I would like to do is right a program that outputs every permutation of that string, that results from removing 0 capital letters, then 1 capital letter, then two capital letters, then all 3.

The reason I'm removing capitals is... you shouldn't focus on capitals. It happened that I needed to remove all the capitals here but , for let's say ADbd, I don't need to remove D. So really, an algorithm for removing a set of already known characters from a string.

So it would output:

ABaC|BaC|AaC|ABa|aC|Aa|Ba|a

Not looking for efficiency here or too brilliant of an algorithm. Something simple and long or short and stupid I am more than happy with as well.

This is part of an ongoing project i'm working on that removes lambda productions (which you fine folk helped me with already) So this is the step where I need to construct the new production rules by removing the nullable variables from the rule, one by one, and so on and output every permutation.

But, y'all can ignore that bit. Think of it just as the string. So, any help is greatly appreciated.

Thank ya kindly.

Was it helpful?

Solution

I'm not sure what language you're working with, so I've provided the high-level steps below.

  1. Walk through your string and create a set capitalIndexes of all the indicies at which capital letters exist.
  2. For each set s in the powerset of capitalIndexes, print out each character of the string except for the those located at an index in s, then print \n.

The only complicated bit here is generating the powerset; here is another answer that provides a means of doing this in C++.

OTHER TIPS

Here you three capital letters and 8 solutions. That should give you an idea (2^3 = 8).

If you have n capital letters, loop through the numbers 0 -> 2^n - 1. For each number you use its binary representation to determine whether a capital letter is included or not.

000 -> a

001 -> aC

010 -> Ba

011 -> BaC

etc.

You didn't specified any language, so I write it in pseudo-language:

Function(string temp, int startindex):

output temp
for i = startindex to temp.length-1 {
  if temp[i] is capital {
    temp.remove(i)
    Function(temp.clone(), i)
  }
}

You start it with Function(temp, 0).

Note that it gives the result possibly in other order than you want. (Not sure from your question how much the order is important for you.)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top