Having trouble groking multiple exclusive combinations in C++
-
15-06-2021 - |
Question
I have an ordered string that I need to present to a user:
ABCCDDCBBBCBBDDBCAAA
Objects represented by 'B' are tagged, such that 2 Bs will have a '~' after them.
AB~CCDDCB~BBCBBDDBCAAA
AB~CCDDCBB~BCBBDDBCAAA
AB~CCDDCBBB~CBBDDBCAAA
and so on...
I've used the combinations library by Howard Hinnant and it works well for this simple case. My test code uses a vector of locations as ints that was sent through for_each_combination.
However, I'm lost as to what to do when I have multiple tags for B.
For example, 4Bs total need to be tagged, 2 by '~' and 2 by '#'
AB~CCDDCB~B#B#CBBDDBCAAA
AB#CCDDCB~B~B#CBBDDBCAAA
AB~CCDDCB#B~B#CBBDDBCAAA
AB#CCDDCB#B~B~CBBDDBCAAA
ABCCDDCB~B~B#CB#BDDBCAAA
and so on...
The pseudocode I've written out is a cascade. After the first for_each_combination, for each of the resulting combinations, copy every other location to another vector and do another for_each_combination.
Considering the number of combinations I will be working with, I'm hoping there's a better way.
Solution 2
I believe I've answered my own question after a bit of looking.
First, I switched from using Howard's library to Hervé's combinations library. The main draw is that using next_combination allows me to chain the combination calculations together, like so:
do {
do {
cout << values << endl;
} while (next_combination(values.begin() + 3, values.begin() + 5, values.end()));
} while (next_combination(values.begin(), values.begin() + 3, values.end()));
I need to massage this into an iterator, but this is exactly what I need.
OTHER TIPS
this sounds like homework, so first of all i'm not going to just give you code, and secondly i added the [homework] tag.
now, with four markers to place, a reasonable solution is a set of nested for loops, four of them
the markers are restricted to 7 positions, so just count from 0 to 6, inclusive
then translate that to positions in the string
then output the string with the markers
i've verified that this is simple to do
if you need further help with it, just ask a new question (and show what you've got so far)