Brute forcing permutations of a string

[Code Apperentice]

Hi all!

I want to make a program where it takes a string input where either the character is an A or B or ?. For example, AB?. Then I want my program to replace the question marks with either A or B and output all the possibilities. So for the string AB it will output AA and AB.

This is for a practice problem in a competitive programming site and I've been stuck on it for a while

[Mantago]

What do you mean? Can you give us your expected output?

[Code Apperentice]

For example:

INPUT
A?B?

OUTPUT:
AABA
AABB
ABBA
ABBB

[Mantago]

OUTPUT:
AABA
AABB
ABBA
ABBB

Should the output be :
OUTPUT:
AABB
ABBA
BAAB
BBBB

[Mantago]

This is for a practice problem in a competitive programming site and I've been stuck on it for a while

Can you give me the link to the website?

[Code Apperentice]

You can only change the question marks and they can only be A or B

[Mantago]

Can you give me the link to the website? So that I can see more of the details?

[Code Apperentice]

I don't know the link my friend screenshotted the problem and this is a step to getting the answer. I just need to know how to create all the possible strings the input string can be provided all the question marks have been changed

[Code Apperentice]

Problem Statement

Bob wants to know all the possible ways he can color a line of tiles. Some of these tiles have certain colors but some can be colored as he wishes. Print all the possible ways he can color the tiles

Input

A string with each character being 'A' for color A, 'B' for color B and '?' for uncolored.

Output

The possible color arrangements

Example Testcase

Input:
A?B?

Output:
AABA
AABB
ABBA
ABBB

[Code Apperentice]

I just wrote what was on the screenshot

[JLBorges]

void print_all( std::string suffix, std::string prefix = {} ) // brute force
{
    const auto pos = suffix.find( '?' ) ;
    if( pos == std::string::npos ) std::cout << prefix << suffix << '\n' ; 
    else for( char c : { 'A', 'B' } ) print_all( suffix.substr(pos+1), prefix + suffix.substr(0,pos) + c ) ;
}

http://coliru.stacked-crooked.com/a/1c6dc1a9dadce65d

[Code Apperentice]

Whoa how does that work?

[JLBorges]

> how does that work?

The output from this noisy version explains the logic:

#include <iostream>
#include <string>
#include <iomanip>

void print_all( std::string suffix, std::string prefix = {}, int nspaces = 0 ) // brute force
{
    std::string tab( nspaces, ' ' ) ;
    std::cout << tab << "prefix: " << std::quoted(prefix) << "  suffix: " << std::quoted(suffix) << '\n' ;
    
    const auto pos = suffix.find( '?' ) ;
    if( pos == std::string::npos ) std::cout << tab << "               =>               " << prefix << suffix << '\n' ;
    else for( char c : { 'A', 'B' } ) print_all( suffix.substr(pos+1), prefix + suffix.substr(0,pos) + c, nspaces+4 ) ;
}

int main()
{
        print_all( "A?B?A?B" ) ;
}

prefix: ""  suffix: "A?B?A?B"
    prefix: "AA"  suffix: "B?A?B"
        prefix: "AABA"  suffix: "A?B"
            prefix: "AABAAA"  suffix: "B"
                           =>               AABAAAB
            prefix: "AABAAB"  suffix: "B"
                           =>               AABAABB
        prefix: "AABB"  suffix: "A?B"
            prefix: "AABBAA"  suffix: "B"
                           =>               AABBAAB
            prefix: "AABBAB"  suffix: "B"
                           =>               AABBABB
    prefix: "AB"  suffix: "B?A?B"
        prefix: "ABBA"  suffix: "A?B"
            prefix: "ABBAAA"  suffix: "B"
                           =>               ABBAAAB
            prefix: "ABBAAB"  suffix: "B"
                           =>               ABBAABB
        prefix: "ABBB"  suffix: "A?B"
            prefix: "ABBBAA"  suffix: "B"
                           =>               ABBBAAB
            prefix: "ABBBAB"  suffix: "B"
                           =>               ABBBABB

http://coliru.stacked-crooked.com/a/e56d3202bce41e46

[Code Apperentice]

Ah I see so for every question mark it uses that as a prefix and uses recursion for each possible A or B!