主页 / 问题 / 580272
Accepted
Surfin Bird
Asked:2020-10-20 01:47:35 +0000 UTC2020-10-20 01:47:35 +0000 UTC

如何在不让元素从其原始位置移动超过给定数量的情况下对数组进行洗牌？

  • 772

如何在不让元素从其原始位置移动超过给定数量 (N) 的情况下对数组进行洗牌？假设 N=1:[1, 2, 3, 4, 5]可以混入[1, 3, 2, 4, 5]or [2, 1, 3, 5, 4]，但不能混入[5, 2, 1, 3, 4].

有没有任何算法？唉，我什么都google不了，我的实现也不是很统一。

但是，以防万一：

/// <summary>
/// Возвращает перемешанный заданным образом массив размером size с элементами от 0
/// до size−1. В дальнейшем этот массив будет использован как список новых позиций.
/// </summary>
/// <param name="size">Число элементов</param>
/// <param name="limit">Максимальное смещение</param>
/// <returns>Перемешанный список индексов</returns>
private int[] Shuffle(int size, int limit) {
    var buffer = new int[size];
    for (var i = 0; i < buffer.Length; i++) {
        buffer[i] = i;
    }

    for (var i = buffer.Length - 1; i >= 0; i--) {
        // Узнаём оригинальную позицию элемента
        var t = buffer[i];

        // Границы для поиска относительно оригинальной позиции
        var a = Math.Max(t - limit, 0);
        var b = Math.Min(t + limit, buffer.Length - 1);

        // Выбираем кандидата на обмен
        var n = _randomInstance.Next(a, b + 1);

        // Самого на себя не меняем
        if (n != i) {
            // Возможные границы обмена для найденного элемента
            var ai = Math.Max(i - limit, 0);
            var bi = Math.Min(i + limit, buffer.Length - 1);

            // Узнаём оригинальную позицию элемента
            var v = buffer[n];

            // Если оригинальная позиция найденного вписывается в границы
            // вокруг i, можно заменить
            if (v >= ai && v <= bi) {
                buffer[i] = buffer[n];
                buffer[n] = t;
            }
        }
    }

    return buffer;
}
алгоритм

2 个回答

  1. Best Answer

    我不知道我的想法是否正确。因为 复杂性对我们来说不是很感兴趣，然后我们重新表述问题，将其减少到最大匹配。我们将有 N * 2 * Delta 阶的边。像往常一样复杂 - O(N^3)。

    结合通过通常的 random_shuffle 进行的随机洗牌，这给出了所有可能的组合，并且或多或少是均匀的（我检查了小 N / Delta）。

    我发布了完整的代码，对生成的一致性进行了最简单的检查。

    关于这种毒瘾的正确性的有趣观点:)

    map<int,int> counter;

void operator delete (void *A){};
void operator delete[] (void *A){};


int n, k;
vector < vector<int> > g;
vector<int> mt;
vector<char> used;

bool try_kuhn (int v) {
    if (used[v])  return false;
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (mt[to] == -1 || try_kuhn (mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}


int main()
{
    int X = 6;
    int MAX_DELTA = 2;
    srand(time(0));

    for (int Z=0;Z<5000;Z++){
        vector<int> first;
        vector<int> firstB;

        for (int i=0;i<X;i++)
            firstB.push_back(i);
        first.resize(X);

        int n = X;
        int k = X;
        g.resize(X);
        for (int i=0;i<X;i++)
            for (int j = max(0,i-MAX_DELTA); j <= min(X-1, i + MAX_DELTA); j++)
                g[i].push_back(j);

        for (int i=0;i<X;i++)
            random_shuffle(g[i].begin(),g[i].end());

        mt.assign (k, -1);
        vector<char> used1 (n);
        for (int i=0; i<n; ++i)
            for (size_t j=0; j<g[i].size(); ++j)
                if (mt[g[i][j]] == -1) {
                    mt[g[i][j]] = i;
                    used1[i] = true;
                    break;
                }
        for (int i=0; i<n; ++i) {
            if (used1[i])  continue;
            used.assign (n, false);
            try_kuhn (i);
        }

        for (int i=0; i<k; ++i)
            if (mt[i] != -1)
                first[mt[i] ] = firstB[i];

        /*for (int i:first)
            cout << i<<" ";
        cout << endl;*/
        int hashC = 0;
        int pow = 1;
        for (int i=0;i<X;i++)
            hashC+=first[i]*pow ,pow*=X;
        counter[hashC]++;

        for (int i=0; i < X;i++)
            if (first[i] - i < -MAX_DELTA || first[i] - i > MAX_DELTA){
                for (int z:first)
                    cout << z<<" ";
                cout <<"FAIL!"<<endl;
                return 0;
            }
        }
        for (auto i : counter){
            int ii = i.first;
            for (int z=0;z<X;z++){
                cout << ii%X<<" ";
                ii/=X;
            }
            cout << " "<<i.second<<endl;
        }
}

    我刚刚从这里复制了匹配代码

    • 3

  2. 尽管如此，我尝试在给定范围内的其他答案中不止一次地实现random_shuffle（即，在 O (n) 时间内洗牌）。

    这不是一个完整的解决方案，而是一个测试想法的工具。与您的版本相比的主要变化是，如果我们不喜欢随机排列，即在我们看来，它们的位置上保留了太多数字，那么我们会尝试重新排列这对数字（或多次，由参数）。

    它使用两个数组 -- a[]-- 洗牌后的数字和p[]-- 洗牌前数字索引的辅助数组，它们会不断变化。数组p用来判断这个数是否可​​以移动到RNG指定的数组索引处？

    这是程序（Linux 上的 gcc/g++）。

    #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>  // для srandom(getpid()) -- если хотим видеть разные результаты в разных запусках

// меняем 2 числа местами если они не уходят со своих мест слишком далеко
static int dswap (int a[], int p[], int i, int j, int d)
{
  int r = 0;

  printf("try swp %d %d (%d,%d)", i, j, a[i], a[j]); // по сути для отладки
  if (p[i] >= j - d && p[i] <= j + d &&
      p[j] >= i - d && p[j] <= i + d) {
    puts("Y");
    r = 1;
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
    t = p[i];
    p[i] = p[j];
    p[j] = t;
  } else {
    ;  // это безобразие, чтобы легче было комментировать печать, когда надоест не нее смотреть
    puts(""); 
  }

  return r;
}

static inline int vmin (int n, int l) {
  return n < l ? n : l;
}

// ./a.out [[-]Nnumbers [Length [Nswaps]]]
int
main (int ac, char *av[])
{
  int n = atoi(av[1] ? av[1] : "10"),         // размер перестановки
    l = atoi(av[1] && av[2] ? av[2] : "5"),   // дистанция
    k = atoi(av[1] && av[2] && av[3] ? av[3] : "1"); // количество попыток "улучшить"
  if (k < 1)
    k = 1;
  if (n < 0) { // если первый параметр < 0, то случайная последовательность перестановок
    n = -n;
    srand(getpid());
  }
  if (n < 3)
    n = 3;
  if (l < 1 || l > n - 1)
    l = n / 2;

  printf("shuffle %d lim = %d k = %d\n", n, l, k);

  int i, j,
    a[n], // тасуемые числа
    p[n]; // их исходные индексы
  for (i = 0; i < n; i++)
    a[i] = i + 10, p[i] = i;

  // сам алгоритм
  for (i = n - 1; i; --i)
    for (j = 0; j < k; j++) // попытки "улучшения случайности"
      if (dswap(a, p, i, i - rand() % vmin(i + 1, l * 2), l)) 
        break;
      else if (j + 1 < k)   // исключительно для наглядности исследований
        puts("rep");


  for (i = 0; i < n; i++)
    printf("%d ", a[i]);

  return puts("") == EOF;
}

    我运行了不同次数的交换尝试（第三个参数），坦率地说，我不明白什么才是更好的。尝试一下，也许您会比其他选项更喜欢其中一个选项。

    • 0

相关问题