Произвольное количество вложенных циклов?

Question

Я хочу взять произвольное количество списков (например, [2, 1, 4 ....], [8, 3, ...], ...) и выбрать номера из каждого списка, чтобыгенерировать все перестановки.Например:

[2, 8, ...], [2, 3, ...], [1, 8, ...], [1, 3, ...], [4, 8, ...], [4, 3, ...], ...

Это легко сделать с помощью вложенных циклов for, но, поскольку я хотел бы, чтобы оно принимало произвольное числоПохоже, что списки должны быть жестко закодированы.По одному на каждый список.Кроме того, поскольку моя программа, вероятно, будет генерировать многие десятки тысяч перестановок, я хотел бы создавать одну перестановку за раз (вместо того, чтобы вычислять их все за один раз и сохранять результат в векторе).Есть ли способ сделать это программно?

Поскольку количество списков известно во время компиляции, я подумал, что, возможно, я мог бы использовать метапрограммирование на основе шаблонов.Однако это кажется неуклюжим и также не соответствует требованию «по одному за раз».Есть предложения?

Answer 1

Вы можете использовать фундаментальный принцип подсчета, например, увеличивая последнюю цифру, пока она не достигнет своего максимального значения, затем увеличивайте вторую последнюю и так далее, как обратный отсчет Вот пример кода, предполагая, что может быть длина различий в списках различий.

#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[n], len[n],i,j;
    for(i = 0 ; i < n ; i++)
    {
        cin>>len[i];
        a[i]=0;
    }
    while(1)
    {
        for(i = 0 ; i< n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        for(j = n-1 ; j>=0 ; j--)
        {
            if(++a[j]<=len[j])
                break;
            else
                a[j]=0;
        }
        if(j<0)
            break;
    }    
    return 0;
}

Попробуйте запустить код с 4 1 1 1 1, и он даст все 4-значные перестановки 0 и 1.

0 0 0 0 
0 0 0 1 
0 0 1 0 
0 0 1 1 
0 1 0 0 
0 1 0 1 
0 1 1 0 
0 1 1 1 
1 0 0 0 
1 0 0 1 
1 0 1 0 
1 0 1 1 
1 1 0 0 
1 1 0 1 
1 1 1 0 
1 1 1 1 

Вы можете использовать 2d массивы для получения комбинаций чисел.

Answer 2

Рекурсивный способ ...

void Recurse(const vector<vector<int>>& v, 
             size_t listToTwiddle, 
             vector<int>& currentPermutation)
{
    // terminate recursion
    if (listToTwiddle == v.size())
    {
        for(auto i = currentPermutation.cbegin(); i != currentPermutation.cend(); ++i)
        {
            cout << *i << " ";
        }
        cout << endl;
        return;
    }

    for(size_t i = 0; i < v[listToTwiddle].size(); ++i)
    {
        // pick a number from the current list
        currentPermutation.push_back(v[listToTwiddle][i]);

        // get all permutations having fixed this number
        Recurse(v, listToTwiddle + 1, currentPermutation);

        // restore back to original state
        currentPermutation.pop_back();
    }
}

void Do(const vector<vector<int>>& v)
{
    vector<int> permutation;
    Recurse(v, 0, permutation);
}

Answer 3

Забавно.

То, что вы, похоже, хотите, на самом деле является своего рода итератором, который будет перебирать заданные диапазоны и на каждом шаге выдает вам перестановку.

Может,как правило, пишутся без метапрограммирования, тем более что шаблоны с переменным числом символов поддерживаются только с C ++ 0x.Тем не менее, я чувствую, что это очень интересный вызов.

Наш первый помощник будет небольшим tuple классом.Нам также понадобится несколько приемов программирования мета-шаблонов для преобразования одного кортежа в другой, но я позволю читателю написать как необходимые функции мета-шаблона, так и фактические функции для выполнения преобразования.(читай: сегодня слишком жарко, чтобы я мог добраться до него).

Вот кое-что, что поможет тебе.

template <class... Containers>
class permutation_iterator
{
public:
  // tuple of values
  typedef typename extract_value<Containers...>::type value_type;

  // tuple of references, might be const references
  typedef typename extract_reference<Containers...>::type reference;

  // tuple of pointers, might be const pointers
  typedef typename extract_pointer<Containers...>::type pointer;

  permutation_iterator(Containers&... containers) { /*extract begin and end*/ }

  permutation_iterator& operator++()
  {
    this->increment<sizeof...(Containers)-1>();
    return *this;
  }

private:
  typedef typename extract_iterator<Containers...>::type iterator_tuple;

  template <size_t N>
  typename std::enable_if_c<N < sizeof...(Containers) && N > 0>::type
  increment()
  {
    assert(mCurrent.at<N>() != mEnd.at<N>());
    ++mCurrent.at<N>();
    if (mCurrent.at<N>() == mEnd.at<N>())
    {
      mCurrent.at<N>() = mBegin.at<N>();
      this->increment<N-1>();
    }
  }

  template <size_t N>
  typename std::enable_if_c<N == 0>::type increment()
  {
    assert(mCurrent.at<0>() != mEnd.at<0>());
    ++mCurrent.at<0>();
  }

  iterator_tuple mBegin;
  iterator_tuple mEnd;
  iterator_tuple mCurrent;
};

Если ты не знаешь, как сделать метаболее простой способ - пойти рекурсивно, а затем попросить пользователя указать, к какому контейнеру он хочет получить доступ, с помощью метода at, взяв N в качестве параметра для указания индекса контейнера.

Answer 4

В STL не было готовой функции для этого, но вы можете написать собственную реализацию, изменив некоторые части next_permutation.

Проблема аналогична реализации двоичной цифрысумматор.Приращение array[0].Если новое значение array[0] переполнено (это означает, что его значение превышает количество имеющихся у вас списков), тогда установите array[0] в ноль и увеличьте array[1].И так далее.

Answer 5

Итак, после дальнейших исследований выясняется, что то, что я пытаюсь сделать, называется декартовым произведением. В итоге я использовал слегка модифицированную версию этого кода. Просто подумал, что обновлю это на тот случай, если кто-нибудь еще наткнется на этот вопрос в поисках того же ответа.

Answer 6

нерекурсивный способ:

#include <vector>
#include <iostream>

// class to loop over space
// no recursion is used
template <class T>
class NLoop{

public:

    // typedefs for readability
    typedef std::vector<T> Dimension;
    typedef std::vector< Dimension > Space;
    typedef std::vector< typename Dimension::iterator > Point;

    // the loop over space and the function-pointer to call at each point
    static void loop(Space space, void (*pCall)(const Point&))
    {

        // get first point in N-dimensional space
        Point current;
        for ( typename Space::iterator dims_it = space.begin() ; dims_it!=space.end() ; ++dims_it )
        {
            current.push_back( (*dims_it).begin() );
        }

        bool run = true;
        while ( run )
        {

            // call the function pointer for current point
            (*pCall)(current);

            // go to next point in space
            typename Space::iterator dims_it = space.begin();
            typename Point::iterator cur_it = current.begin();
            for (  ; dims_it!=space.end() ; ++dims_it, ++cur_it )
            {
                // check if next in dimension is at the end
                if ( ++(*cur_it) == (*dims_it).end() )
                {
                    // check if we have finished whole space
                    if ( dims_it == space.end() - 1 )
                    {
                        // stop running now
                        run = false;
                        break;
                    }
                    // reset this dimension to begin
                    // and go to next dimension
                    *cur_it = (*dims_it).begin();
                }
                else
                {
                    // next point is okay
                    break;
                }
            }

        }
    }
};


// make typedef for readability
// this will be a loop with only int-values in space
typedef NLoop<int> INloop;

// function to be called for each point in space
// do here what you got to do
void call(const INloop::Point &c)
{
    for ( INloop::Point::const_iterator it = c.begin() ; it!=c.end() ; ++it)
    {
        std::cout << *(*it) << " ";
    }
    std::cout << std::endl;
}

int main()
{

    // fill dimension
    INloop::Dimension d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    // fill space with dimensions
    INloop::Space s;
    s.push_back(d);
    s.push_back(d);
    s.push_back(d);

    // loop over filled 'space' and call 'call'
    INloop::loop(s,call);

    return 0;

}

Answer 7

Используя рекурсию, вы, вероятно, могли бы «прокормить себя» текущей позицией, оставшимися списками и так далее. Это может привести к переполнению, но часто рекурсивную функцию можно превратить в нерекурсивную (как в цикле for), хотя большая часть элегантности исчезает.