3

I wanna list all arrangement, the following is my sample code:

const unsigned char item1[] = {'b'};
const unsigned char item2[] = { 'A', 'C' ,'D'};
const unsigned char item3[] = {'1','2'};

int _tmain(int argc, _TCHAR* argv[])
{
    for (int i = 0; i < sizeof(item1) / sizeof(unsigned char); i++){
        for (int j = 0; j < sizeof(item2) / sizeof(unsigned char); j++){
            for (int k = 0; k < sizeof(item3) / sizeof(unsigned char); k++){
                printf("%c%c%c\n",item1[i],item2[j],item3[k]);
            }
        }
    }
    return 0;
}

This will print all arrangement, but I am worried about if the array item is from item1 to item99, the code is difficult to maintain. Is there a better solution to print all arrangement? Thanks!

Azeem
  • 11,148
  • 4
  • 27
  • 40
Tu Roland
  • 65
  • 9
  • 2
    I don't say better, but what you are looking for is probably a vector of vectors, handled with recursive functions. – Yunnosch Apr 20 '18 at 06:14
  • 1
    You can reduce array length calculation with `#define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))` – pbn Apr 20 '18 at 06:15
  • 2
    @Hamed I am not sure what you mean by "a couple loops". I understand "a couple of loops" == "a very few loops". OPs 'item1' to 'item99' seems like they are talking about 100 items to be handled by 100 loops, that stays applicable when changing to a vector of vectors. I probably misunderstand your meaning. Feel free to elaborate. – Yunnosch Apr 20 '18 at 06:20
  • 2
    @Hamed, he needs show all combinations, for n=100, it's 1000000 combinations, and for three arrays athat's three lop statements – Swift - Friday Pie Apr 20 '18 at 06:22
  • provincially there is no really effective other way, but you probably would want to use range for statment instead of traditional for. Range for works for statically declared arrays and works with `std `containers as well, would remove all that sizeof fluff (it would be used as `std::end()`). Also, do you ask about C or C++? two different languages – Swift - Friday Pie Apr 20 '18 at 06:24
  • Assuming that OPs question is mostly about constructing the loops, allow me to refer to an almost-duplicate in C. https://stackoverflow.com/questions/49265552/nesting-for-loop-n-times/49265629#49265629 – Yunnosch Apr 20 '18 at 06:26
  • @Swift What do you mean by "provincially"? I do not get it. – Yunnosch Apr 20 '18 at 06:34
  • What if your arrays all contain just two elements, "0" and "1"? Can you predict what output you will get? How about "0" "1" and "2"? And the last step is to make them contain different number of elements. – n. m. could be an AI Apr 20 '18 at 06:37
  • @n.m. I think you should phrase your contribution more explicitly. I for example do not get the abstract indirect hints you give. – Yunnosch Apr 20 '18 at 06:41
  • 3
    If you want to do this for 2 items per array and 100 different arrays, be prepared to wait. If the average loop duration is 1ns, the total time taken is roughly 40 billion years. about 4 times longer than the universe has existed... – Mats Petersson Apr 20 '18 at 06:50
  • 1
    @MatsPetersson That’s a bit of an exaggeration; 40 billion years is a bit less than 3 times the age of the universe. But you also missed a factor of 1000 and it’s actually more like 3,000 times the age of the universe instead of 3. – Daniel H Apr 20 '18 at 07:53
  • @Yunnosch I blame Swipe for random words – Swift - Friday Pie Apr 20 '18 at 07:57
  • @DanielH Not every day you would see an argument about age of Universe on a programming website – Swift - Friday Pie Apr 20 '18 at 08:03
  • You want to iterate through all elements of the [Cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) of the several containers. There is a number of known solutions for this problem. Look at [this question](https://stackoverflow.com/q/13813007/3043539), for example. – Constructor Apr 20 '18 at 11:39
  • @Yunnosch the best way to figure it out is to look at the actual program output for these simplistic cases and then infer further insights from there. – n. m. could be an AI Apr 20 '18 at 12:51

2 Answers2

2

You might store your "iterator" in vector, then you might do something like:

bool increase(const std::vector<std::string>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] == v[index].size()) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

void do_job(const std::vector<std::string>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = v.size(); i != size; ++i) {
        std::cout << v[i][it[i]];
    }
    std::cout << std::endl;
}

void iterate(const std::vector<std::string>& v)
{
    std::vector<std::size_t> it(v.size(), 0);

    do {
        do_job(v, it);
    } while (increase(v, it));
}

Demo

Jarod42
  • 203,559
  • 14
  • 181
  • 302
1

A nice way of accomplishing this is to look at the problem as an integer base conversion problem. So, the total number of combinations is the product of all the array sizes. The output string n would be enough to determine the array indeces that should be printed in the string. Since you have tagged it as a C++ question I would use 2-D vectors, as this makes life much simpler:

int _tmain(int argc, _TCHAR* argv[])
{
    // Initialize the vector
    vector<vector<char>> v( 3 );

    v[0].push_back( 'b' );
    v[1].push_back( 'A' );
    v[1].push_back( 'C' );
    v[1].push_back( 'D' );
    v[2].push_back( '1' );
    v[2].push_back( '2' );

    // This is a convenience vector of sizes of each 1-D vector
    vector<size_t> sizes( v.size() );

    // Get the total number of combinations and individual vector
    // sizes
    size_t total = 1;
    for( size_t i = 0; i < v.size(); ++i )
    {
        sizes[i] = v[i].size();
        total *= sizes[i];
    }

    size_t done = 0;

    // Loop till all the combinations are printed
    while( done != total )
    {
        // Remainder, which is the index of the element
        // in the 1-D vector that is to be printed
        size_t r = 0;
        // Quotient to be used for the next remainder
        size_t q = done;
        // Combination to be printed
        string s = "";

        // Loop over the 1-D vectors, picking the correct
        // character from each
        for( size_t i = 0; i < v.size(); ++i )
        {
            r = q % sizes[v.size() - 1 - i];
            q = static_cast<size_t>( floor( q/sizes[v.size() - 1 - i] ) );
            s = v[v.size() - 1 - i][r] + s;
        }

        cout<<s<<"\n";

        done++;
    }
    return 0;
}
mahesh
  • 1,028
  • 10
  • 24