Эффективный способ перечислить все k-перестановки n объектов при соблюдении определенного критерия

avatar
vxs8122
8 апреля 2018 в 00:17
134
1
1

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

Вот моя попытка.

Предположим, что n = 3, k = 3. Пусть 0 обозначает пустой объект.

Некоторые возможные примеры:

011 101 110 112
012 102 120 113
013 103 130 121
... ... ... ...
033 303 330 332

Итак, я создаю "пул" {0, 1, 1, 2, 2, 3, 3}. Три объекта будут выбраны из пула с помощью перестановки логического вектора (например, логический вектор { 0, 1, 0, 0, 0, 1, 1 } выбирает 1, 3, 3 из пула)

Затем все перестановки трех выбранных объектов добавляются в набор.

Однако... будет некоторое повторение, так как { 0, 1, 0, 0, 0, 1, 1 } считается эквивалентным { 0, 0, 1, 0, 0, 1, 1, } как оба выберут 1, 3, 3 из пула.

Этот код становится довольно затратным в вычислительном отношении для более высоких n и k, например, когда n = 8 и k = 6. Есть ли более эффективный способ сделать это?

Мой код C++:

set< vector<int> > generate_kperms ( int n, int k )
{

  set< vector<int> > kperms;

  // create vector of integers { 0, 1, 1, 2, 2, ...  n, n }
  vector<int> pool( 2*n + 1 );
  pool[0] = 0;
  for ( int i = 1; i <= n; ++i )
    pool[2*i-1] = pool[2*i] = i;

  // create logical vector with k true values, to be permuted
  vector<bool> logical( pool.size() );
  fill( logical.end()-k, logical.end(), true );

  do {
    vector<int> kperm( k );
    vector<int>::iterator itr = kperm.begin();
    for ( int idx = 0; idx < (int) pool.size(); ++idx ) {
      if ( logical[idx] )
        *(itr++) = pool[idx];
    }
    do {
      kperms.insert( kperm );
    } while ( next_permutation ( kperm.begin(), kperm.end() ) );
  } while ( next_permutation( logical.begin(), logical.end() ) );

  return kperms;

}       /* -----  end of function generate_kperms  ----- */
Источник

Ответы (1)

avatar
David Eisenstat
8 апреля 2018 в 01:27
2

Обратите внимание, что если вы сгенерируете все перестановки pool, то префиксы длины k будут почти такими, как вы хотите, только с большим количеством последовательных дубликатов. Простой, но достойный способ сгенерировать все k-перестановки состоит в том, чтобы пропустить дубликаты, отсортировав суффикс n - k по убыванию перед вызовом next_permutation. А именно, 

#include <iostream>
#include <set>
#include <vector>

using std::cout;
using std::greater;
using std::sort;
using std::vector;

vector<vector<int>> generate_kperms(int n, int k) {
  vector<vector<int>> kperms;
  vector<int> pool(2 * n + 1);
  pool[0] = 0;
  for (int i = 1; i <= n; ++i) {
    pool[2 * i - 1] = pool[2 * i] = i;
  }
  do {
    kperms.push_back(vector<int>(pool.begin(), pool.begin() + k));
    sort(pool.begin() + k, pool.end(), greater<int>());
  } while (next_permutation(pool.begin(), pool.end()));
  return kperms;
}

int main() {
  for (const vector<int> &kperm : generate_kperms(8, 6)) {
    for (int x : kperm) {
      cout << x << ' ';
    }
    cout << '\n';
  }
}

Возможно, вы сможете увеличить скорость, внедрив собственную версию next_permutation, которая обрабатывает суффикс n - k как отсортированный в обратном порядке, но я не могу найти его в Кнуте 4A прямо сейчас.