使用最少的内存和时间查找数组的顺序

Question

假设我有一个包含 5 个元素的数组。我的程序知道它总是 5 个元素，并且在排序时它总是只有 1、2、3、4、5。

根据排列公式即 n!/(n-r)!我们可以通过 120 种方式订购。

在 C++ 中使用 std::next_permutation 我可以生成所有这 120 个订单。

现在，我的 program/routine 接受输入参数作为 1 到 120 范围内的数字，并给出数组的特定顺序作为输出。

这适用于小数组大小，因为我可以重复 std::next_permutation 直到匹配输入参数。

真正的问题是，如果我的数组有 25 个或更多元素，我怎样才能在更短的时间内完成？对于 25 个元素，可能的订单数为：15511210043330985984000000.

有没有一种技术可以让我使用给定的数字作为输入轻松找到数字的顺序？

提前致谢:)

Answer 1

我有一个类似的问题，我在 Gtk TreeView 中存储了很多行，并且不想每次都想通过它的位置而不是通过它的引用访问行时遍历所有这些行。

所以，我创建了一个行位置图，这样我就可以通过我需要的参数轻松识别它们。所以，我对此的建议是你遍历所有排列一次并将每个 std::permutation 映射到一个数组中（我使用了 std::vector），这样你就可以通过 myVector[permutation_id].[=14 访问它=]

这是我完成映射的方式：

vector<int> FILECHOOSER_MAP;
void updateFileChooserMap() {
    vector<int> map;
    TreeModel::Children children = getInterface().getFileChooserModel()->children();
    int i = 0;
    for(TreeModel::Children::iterator iter = children.begin(); iter != children.end(); iter++) {
        i++;
        TreeModel::Row row = *iter;
        int id = row[getInterface().getFileChooserColumns().id];
        if( id >= map.size()) {
            for(int x = map.size(); x <= id; x++) {
                map.push_back(-1);
            }
        }
        map[id] = i;
    }
    FILECHOOSER_MAP = map;
}

因此，在您的情况下，您只需像这样遍历排列，并且可以以允许您通过其 ID 访问它们的方式映射它们。

希望对你有帮助:D 问候，tagelicht

Answer 2

这是 this link 中提到的算法的示例 C++ 实现：

#include <vector>
#define ull unsigned long long

ull factorial(int n) {
    ull fac = 1;
    for (int i = 2; i <= n; i++)
        fac *= i;
    return fac;
}

std::vector<int> findPermutation(int len, long idx) {
    std::vector<int> original = std::vector<int>(len);
    std::vector<int> permutation = std::vector<int>();
    for (int i = 0; i < len; i++) {
        original[i] = i;
    }

  ull currIdx = idx;
  ull fac = factorial(len);
  while (original.size() > 0) {
      fac /= original.size();
      int next = (currIdx - 1) / fac;
      permutation.push_back(original[next]);
      original.erase(original.begin() + next);
      currIdx -= fac * next;
  }
  return permutation;
}

findPermutation 函数接受原始字符串的长度和所需排列的索引，以及 returns 表示该排列的数组。例如，[0, 1, 2, 3, 4] 是任何长度为 5 的字符串的第一个排列，[4, 3, 2, 1, 0] 是最后一个（第 120 个）排列。

使用最少的内存和时间查找数组的顺序

Find order of an array using minimum memory and time

c++

arrays

sorting

permutation