Сочетание коллекции с повторениями

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

Уже есть прецедент для этого в стандартной библиотеке. Например lower_bound который мы на самом деле будем использовать в этом решении. Однако при общем использовании это может потребовать от пользователя сортировки перед передачей.

Функция, которую мы напишем для этого, будет принимать итераторы для отсортированной коллекции, из которой следует извлечь следующую комбинацию, и итераторы для текущей комбинации. Нам также понадобится размер, но он может быть получен из расстояния между итераторами комбинации.

template <typename InputIt, typename OutputIt>
bool next_combination(InputIt inFirst, InputIt inLast, OutputIt outFirst, OutputIt outLast) {
assert(distance(inFirst, inLast) >= distance(outFirst, outLast));

const auto front = make_reverse_iterator(outFirst);
const auto back = make_reverse_iterator(outLast);
auto it = mismatch(back, front, make_reverse_iterator(inLast)).first;

const auto result = it != front;

if (result) {
auto ub = upper_bound(inFirst, inLast, *it);

copy(ub, next(ub, distance(back, it) + 1), next(it).base());
}
return result;
}

Эта функция написана в формате других функций алгоритма, поэтому с ней можно использовать любой контейнер, поддерживающий двунаправленные итераторы. Для нашего примера, хотя мы будем использовать: const vector<unsigned int> row{ 40U, 40U, 40U, 50U, 50U, 60U, 100U }; который обязательно сортируется:

vector<unsigned int> it{ row.cbegin(), next(row.cbegin(), 3) };

do {
copy(it.cbegin(), it.cend(), ostream_iterator<unsigned int>(cout, " "));
cout << endl;
} while(next_combination(row.cbegin(), row.cend(), it.begin(), it.end()));

Живой пример

После написания этого ответа я провел немного больше исследований и нашел N2639 который предлагает стандартизированный next_combination, который был:

• Активно рассматривается для будущего TR, когда работа над TR2 была отложена в ожидании
• Рассмотрено положительно в то время
• По крайней мере, еще один пересмотр перед любым усыновлением
• Необходима доработка, чтобы отразить добавление возможностей языка C ++ 11

Использование эталонной реализации N2639 требует изменчивости, поэтому мы будем использовать: vector<unsigned int> row{ 40U, 40U, 40U, 50U, 50U, 60U, 100U };, И наш пример кода становится:

vector<unsigned int>::iterator it = next(row.begin(), 3);

do {
copy(row.begin(), it, ostream_iterator<unsigned int>(cout, " "));
cout << endl;
} while(next_combination(row.begin(), it, row.end()));

Живой пример

Вот класс, который я однажды написал во времена моего университета, чтобы обращаться с бозонами. Он довольно длинный, но в целом его можно использовать и, кажется, он хорошо работает. Кроме того, он также дает функции ранжирования и отмены рейтинга. Надеюсь, это поможет — но никогда не спрашивайте меня, чем я тогда занимался … 😉

struct SymmetricIndex
{
using StateType = std::vector<int>;
using IntegerType = int;
int M;
int N;
StateType Nmax;
StateType Nmin;
IntegerType _size;
std::vector<IntegerType> store;
StateType state;
IntegerType _index;

SymmetricIndex() = default;
SymmetricIndex(int _M, int _N, int _Nmax = std::numeric_limits<int>::max(), int _Nmin = 0)
: SymmetricIndex(_M, _N, std::vector<int>(_M + 1, std::min(_Nmax, _N)), StateType(_M + 1, std::max(_Nmin, 0)))
{}

SymmetricIndex(int _M, int _N, StateType const& _Nmax, StateType const& _Nmin)
: N(_N)
, M(_M)
, Nmax(_Nmax)
, Nmin(_Nmin)
, store(addressArray())
, state(M)
, _index(0)
{
reset();
_size = W(M, N);
}

friend std::ostream& operator<<(std::ostream& os, SymmetricIndex const& sym);

SymmetricIndex& reset()
{
return setBegin();
}bool setBegin(StateType& state, StateType const& Nmax, StateType const& Nmin) const
{
int n = N;
for (int i = 0; i<M; ++i)
{
state[i] = Nmin[i];
n -= Nmin[i];
}

for (int i = 0; i<M; ++i)
{
state[i] = std::min(n + Nmin[i], Nmax[i]);
n -= Nmax[i] - Nmin[i];
if (n <= 0)
break;
}

return true;
}SymmetricIndex& setBegin()
{
setBegin(state, Nmax, Nmin);
_index = 0;
return *this;
}bool isBegin() const
{
return _index==0;
}

bool setEnd(StateType& state, StateType const& Nmax, StateType const& Nmin) const
{
int n = N;
for (int i = 0; i < M; ++i)
{
state[i] = Nmin[i];
n -= Nmin[i];
}

for (int i = M - 1; i >= 0; --i)
{
state[i] = std::min(n + Nmin[i], Nmax[i]);
n -= Nmax[i] - Nmin[i];
if (n <= 0)
break;
}
return true;
}
SymmetricIndex& setEnd()
{
setEnd(state, Nmax, Nmin);
_index = _size - 1;
return *this;
}

bool isEnd() const
{
return _index == _size-1;
}

IntegerType index() const
{
return _index;
}

IntegerType rank(StateType const& state) const
{
IntegerType ret = 0;
int n = 0;

for (int i = 0; i < M; ++i)
{
n += state[i];
for (int k = Nmin[i]; k < state[i]; ++k)
ret += store[(n - k) * M + i];
}

return ret;
}

IntegerType rank() const
{
return rank(state);
}

StateType unrank(IntegerType rank) const
{
StateType ret(M);

int n = N;
for (int i = M-1; i >= 0; --i)
{
int ad = 0;
int k = std::min(Nmax[i] - 1, n);

for (int j = Nmin[i]; j <= k; ++j)
ad+=store[(n - j) * M + i];

while (ad > rank && k >= Nmin[i])
{
ad -= store[(n - k) * M + i];
--k;
}

rank -= ad;
ret[i] = k+1;
n -= ret[i];
if (n <= 0)
{
return ret;
}
}

return ret;
}

IntegerType size() const
{
return _size;
}

operator StateType& ()
{
return state;
}

auto operator[](int i) -> StateType::value_type& { return state[i]; }

operator StateType const& () const
{
return state;
}
auto operator[](int i) const -> StateType::value_type const& { return state[i]; }bool nextState(StateType& state, StateType const& Nmax, StateType const& Nmin) const
{
//co-lexicographical ordering with Nmin and Nmax:

// (1) find first position which can be decreased
//     then we have state[k] = Nmin[k]  for k in [0,pos]
int pos = M - 1;
for (int k = 0; k < M - 1; ++k)
{
if (state[k] > Nmin[k])
{
pos = k;
break;
}
}

// if nothing found to decrease, return
if (pos == M - 1)
{
return false;
}

// (2) find first position after pos which can be increased
//     then we have state[k] = Nmin[k]  for k in [0,pos]
int next = 0;
for (int k = pos + 1; k < M; ++k)
{
if (state[k] < Nmax[k])
{
next = k;
break;
}
}
if (next == 0)
{
return false;
}
--state[pos];
++state[next];

// (3) get occupation in [pos,next-1] and set to Nmin[k]
int n = 0;
for (int k = pos; k < next; ++k)
{
n += state[k] - Nmin[k];
state[k] = Nmin[k];
}

// (4) fill up from the start
for (int i = 0; i<M; ++i)
{
if (n <= 0)
break;
int add = std::min(n, Nmax[i] - state[i]);
state[i] += add;
n -= add;
}

return true;
}SymmetricIndex& operator++()
{
bool inc = nextState(state, Nmax, Nmin);
if (inc) ++_index;
return *this;
}
SymmetricIndex operator++(int)
{
auto ret = *this;
this->operator++();
return ret;
}

bool previousState(StateType& state, StateType const& Nmax, StateType const& Nmin) const
{
////co-lexicographical ordering with Nmin and Nmax:

// (1) find first position which can be increased
//     then we have state[k] = Nmax[k]  for k in [0,pos-1]
int pos = M - 1;
for (int k = 0; k < M - 1; ++k)
{
if (state[k] < Nmax[k])
{
pos = k;
break;
}
}

// if nothing found to increase, return
if (pos == M - 1)
{
return false;
}

// (2) find first position after pos which can be decreased
//     then we have state[k] = Nmin[k]  for k in [pos+1,next]
int next = 0;
for (int k = pos + 1; k < M; ++k)
{
if (state[k] > Nmin[k])
{
next = k;
break;
}
}
if (next == 0)
{
return false;
}
++state[pos];
--state[next];

int n = 0;
for (int k = 0; k <= pos; ++k)
{
n += state[k] - Nmin[k];
state[k] = Nmin[k];
}
if (n == 0)
{
return true;
}

for (int i = next-1; i>=0; --i)
{
int add = std::min(n, Nmax[i] - state[i]);
state[i] += add;
n -= add;
if (n <= 0)
break;
}

return true;
}SymmetricIndex operator--()
{
bool dec = previousState(state, Nmax, Nmin);
if (dec) --_index;
return *this;
}
SymmetricIndex operator--(int)
{
auto ret = *this;
this->operator--();
return ret;
}

int multinomial() const
{
auto v = const_cast<std::remove_reference<decltype(state)>::type&>(state);
return multinomial(v);
}

int multinomial(StateType& state) const
{
int ret = 1;
int n = state[0];
for (int i = 1; i < M; ++i)
{
n += state[i];
ret *= binomial(n, state[i]);
}
return ret;
}

SymmetricIndex& random(StateType const& _Nmin)
{
static std::mt19937 rng;

state = _Nmin;
int n = std::accumulate(std::begin(state), std::end(state), 0);
auto weight = [&](int i) { return state[i] < Nmax[i] ? 1 : 0; };

for (int i = n; i < N; ++i)
{
std::discrete_distribution<int> d(N, 0, N, weight);
++state[d(rng)];
}
_index = rank();

return *this;
}
SymmetricIndex& random()
{
return random(Nmin);
}

private:
IntegerType W(int m, int n) const
{
if (m < 0 || n < 0) return 0;
else if (m == 0 && n == 0) return 1;
else if (m == 0 && n > 0) return 0;
//else if (m > 0 && n < Nmin[m-1]) return 0;
else
{
//static std::map<std::tuple<int, int>, IntegerType> memo;

//auto it = memo.find(std::make_tuple(k, m));
//if (it != std::end(memo))
//{
//  return it->second;
//}

IntegerType ret = 0;
for (int i = Nmin[m-1]; i <= std::min(Nmax[m-1], n); ++i)
ret += W(m - 1, n - i);

//memo[std::make_tuple(k, m)] = ret;
return ret;
}
}

IntegerType binomial(int m, int n) const
{
static std::vector<int> store;
if (store.empty())
{
std::function<IntegerType(int, int)> bin = [](int n, int k)
{
int res = 1;

if (k > n - k)
k = n - k;

for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}

return res;
};

store.resize(M*M);
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < M; ++j)
{
store[i*M + j] = bin(i, j);
}
}
}
return store[m*M + n];
}

auto addressArray() const -> std::vector<int>
{
std::vector<int> ret((N + 1) * M);

for (int n = 0; n <= N; ++n)
{
for (int m = 0; m < M; ++m)
{
ret[n*M + m] = W(m, n);
}
}
return ret;
}
};

std::ostream& operator<<(std::ostream& os, SymmetricIndex const& sym)
{
for (auto const& i : sym.state)
{
os << i << " ";
}
return os;
}

Используйте это как

int main()
{
int M=4;
int N=3;
std::vector<int> Nmax(M, N);
std::vector<int> Nmin(M, 0);
Nmax[0]=3;
Nmax[1]=2;
Nmax[2]=1;
Nmax[3]=1;

SymmetricIndex sym(M, N, Nmax, Nmin);

while(!sym.isEnd())
{
std::cout<<sym<<"   "<<sym.rank()<<std::endl;
++sym;
}
std::cout<<sym<<"   "<<sym.rank()<<std::endl;
}

Это будет выводить

3 0 0 0    0    (corresponds to {40,40,40})
2 1 0 0    1    (-> {40,40,50})
1 2 0 0    2    (-> {40,50,50})
2 0 1 0    3    ...
1 1 1 0    4
0 2 1 0    5
2 0 0 1    6
1 1 0 1    7
0 2 0 1    8
1 0 1 1    9
0 1 1 1    10   (-> {50,60,100})

DEMO

Обратите внимание, что я предположил здесь восходящее отображение элементов вашего множества (то есть число 40 задается индексом 0, число 50 указывается индексом 1 и т. Д.).

Точнее: превратить ваш список в map<std::vector<int>, int> лайк

std::vector<int> v{40,40,40,50,50,60,100};

std::map<int, int> m;

for(auto i : v)
{
++m[i];
}

Тогда используйте

int N = 3;
int M = m.size();
std::vector<int> Nmin(M,0);
std::vector<int> Nmax;
std::vector<int> val;

for(auto i : m)
{
Nmax.push_back(m.second);
val.push_back(m.first);
}

SymmetricIndex sym(M, N, Nmax, Nmin);

как вход в SymmetricIndex учебный класс.

Чтобы распечатать вывод, используйте

    while(!sym.isEnd())
{
for(int i=0; i<M; ++i)
{
for(int j = 0; j<sym[i]; ++j)
{
std::cout<<val[i]<<" ";
}
}
std::cout<<std::endl;
}

for(int i=0; i<M; ++i)
{
for(int j = 0; j<sym[i]; ++j)
{
std::cout<<val[i]<<" ";
}
}
std::cout<<std::endl;

Все не проверено, но это должно дать идею.