如何提高生成下一个词典排列的算法的效率？

Question

这里必须注意的是,我在纸上手工进行了数学计算,以得出上述证明.我不确定单独使用现代计算机的介质是否会证明这些证据.

下面使用的"效率"的定义意味着在最短的时间内完成算法的离散部分或整个算法.数学上,编程上或计算上都是如此.

在进一步检查从原始集合或当前排列生成下一个词典排列的程序时,在没有递归函数调用的情况下重新阅读@chqrlie在Permutations的答案之后,我开始通过在纸上写索引来试图观察任何可用于执行特定任务的索引之间的数学关系.

我发现了几个有趣的事实,其证据如下所示.

例如,当我们写出值时

a,b,c

要么

abc

或者,编写代表值的索引

0,1,2

要么

012

既然我们知道,给定一套

abc

我们可以通过交换集合的最后两个值或索引来生成下一个词典排列

acb

要么

021

我们可以忽略可能是任何类型数据的值,并专注于使用索引进行检查,因为离散数更适合关联可能的关系而不是可能无限多样化的值.

因此,用原始集的第二个词典索引

abc

我们可以将索引的值表示为数字,并观察

0,2,1

要么

021

第一个索引是

012

第二个是

021

既然我们知道.length原始集合是3,如果我们记住.length原始值集合,我们可以删除起始

0

在哪里将索引减少到数字

12

和

21

分别.其中0可以作为原始集合的索引引用0,以便在下一个操作的结果集小于原始集合时获取索引处的值.

当我们尝试绘制12和之间的潜在关系时21,我们发现了这一点

21 - 12 = 9

当我们继续时,我们发现下一个词典索引是

102

减去以前的索引

102 - 21 = 81

102下一个词典排列在哪里,表示为值

bac

它为我们提供了数字9之间的共同关系,用数字表示

9

对于表示为数字的无限输入值集合,这种关系是明显的和可再现的.我们可以根据观察者的视角,将关系图绘制成两个斜率,当从结果排列集的第一个值开始绘制图形时,它具有倒置的顶点偏移

// graph 1
0,9,81

// graph 2
abc 012 0
acb 021 1 9
bac 102 2 81
bca 120 3 18
cab 201 4 81
cba 210 5 9

 /\/\
/    \

我们可以在这里观察到,倾斜斜率上的图上的数字与相应的下倾斜率处的数字相同,在可能的排列的总数除以一半的数量的反转之后,其中例如总数在六个排列中,我们减去一个,留下五个剩余部分,记住我们仍然需要奇数组索引,我们使用倒顶点处的数字作为枢轴,留下四个指数,我们分别表示倾斜和倾斜斜率.

我们在此观察到,赤纬斜率图上的数字与相同y坐标处的倾斜斜率的相应相邻角度相同.

因此,下面我演示了一个证据,即通过利用数字9的加法或乘法,可以计算,生成,过滤,得到无限输入集的无限置换集.

9

通过匹配仅包括输入数字的索引号的数字,在集合中没有重复.

此外,我证明了需要仅需要索引作为倾斜斜率上的数字,或者可能的排列除以2加1的总量,以得出给定输入的排列总数.

正如本文前言所强调的那样,如果没有很多时间在纸上进行数学计算,这种计算可能是不可能实现的.简单的媒体屏幕不提供与在纸上逐个组成字符相同的媒体; 能够从各种物理尺寸查看纸张.

使用编码语言的算法表达本身就是另一项任务.

以下是使用"JavaScript"编程语言实现的发现,证明和表达的进展.RegExp正如@Tushar所指出的那样,第一个版本的预期结果与预期结果不准确RegExp,但已更正,但错误的RegExp返回结果相同.

给定输入为数组

var arr = ["a", "b", "c", "d"];

// version 1

function getNextLexicographicPermutation(arr) {
  var len = arr.length;
  var idx = arr.map(function(_, index) {
    return index
  });
  var re = new RegExp("[" + len + "-9]|(.)(?!=\\1)");
  var n = Math.pow(10, len - 1);
  var p = 9;
  var last = Number(idx.slice().reverse().join(""));
  var res = [idx];
  var curr = Number(res[res.length - 1].join(""));
  while (curr < last) {
    for (var prev = curr, next, k; prev <= last; prev += p) {
      if ((re.test(prev))) {
        k = String(prev);
        if (k.length >= len - 1) { //  && Math.max.apply(Math, j) < len
          next = [];
          for (var i = 0; i < k.length; i++) {
            if (next.indexOf(Number(k[i])) == -1 
              && idx.indexOf(Number(k[i])) !== -1) {
                next.push(Number(k[i]))
            }
          }
          if (prev < n && next.length === len - 1 
             || next.length === len && prev > curr) {
               res[res.length] = next.length < len 
                                 ? [0].concat.apply([0], next) 
                                 : next;
          }
        }
      }
      curr = prev;
    }
  };
  return res.map(function(value) {
    return value.map(function(index) {
      return arr[index]
    })
  })
}

getNextLexicographicPermutation(arr);

作为数组索引的数字之间的数字差异图arr将是

// graph 3
// reflecting input `abcd`
[9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9]

// version 2.0 without using `RegExp`

function getNextLexicographicPermutation(arr) {
  var len = arr.length;
  var idx = arr.map(function(_, index) {
    return index
  });
  var n = Math.pow(10, len - 1);
  var p = 9;
  var last = Number(idx.slice().reverse().join(""));
  var res = [];
  var curr = Number(idx.join(""));
  var prev, k, next;

  while (curr <= last) {
    prev = curr;            
    k = String(prev).split("").map(Number);
    if (k.every(function(v) {
        return idx.indexOf(v) !== -1
      }) && k.length >= len - 1) {
      next = [];
      for (var i = 0; i < k.length; i++) {
        if (next.indexOf(Number(k[i])) == -1 
          && idx.indexOf(Number(k[i])) !== -1) {
            next.push(Number(k[i]))
        }
      }
      if (prev < n && next.length === len - 1 
          || prev > n && next.length === len)) {
        res[res.length] = next.length < len 
                          ? [0].concat.apply([0], next) 
                          : next;
      }
    }
    prev += p;
    curr = prev;
  };
  return res.map(function(item) {
    return item.map(function(v) {
      return arr[v]
    })
  })
}
getNextLexicographicPermutation(arr)

第二个版本的效率比第一个版本大大提高了,通过用RegExp@lleaff的答案代替bitmask,以最有效的方法检查数字范围内的数字而不重复.

版本和位掩码版本DevTools之间生成的相关配置文件RegExp应该在chrome浏览器中可以重新编写,但由于忽略了对所执行的确切测试的评论,因此无法精确地重现所发布的数字和时间,而无需花费更多时间来验证之前发布的数字.题.记不清楚,虽然当.length输入设置为10 时浏览器选项卡可能已崩溃.重要的是bitmask测试版比RegExp测试版更有效.

// version 2.1, substituting bitmask for `RegExp`

function getNextLexicographicPermutation(arr) {
  function checkDigits(min, max, n) {
    var digits = 0;
    while (n) {
      d = (n % 10);
      n = n / 10 >> 0;
      if (d < min || d > max || (digits & (1 << d)))
        return false;
      else
        digits |= 1 << d;
    }
    return true;
  }
  var len = arr.length,
    idx = arr.map(function(_, index) {
      return index
    }),
    p = 9,
    min = 0,
    max = len - 1,
    last = Number(idx.slice().reverse().join("")),
    res = [],
    curr = Number(idx.join("")),
    next;

  while (curr < last) {
    next = (curr += p);
    if (checkDigits(min, max, next)) res[res.length] = next;
    curr = next;
  };

  return res.map(function(item) {
    var item = String(item).split("").map(Number);
    item = item.length < arr.length ? [0].concat(item) : item;
    return item.map(function(index) {
      return arr[index]
    }).filter(Boolean)
  })
}    
getNextLexicographicPermutation(arr);

这些笔记和流程在一年多的时间里花了一年多的时间来展示和证明.主要是简单地考虑如何同时使用斜率斜率索引获得斜率两侧的索引,而不是编码算法.

数学的大部分是试图得出9号的相邻倍数之间的进一步相关性,因为能够计算9号的确切下一个倍数.

9 

将数字递增9,然后从结果数字中过滤重复值.我还没有能够解释倾斜斜率上相邻9的倍数之间的相互关系到乘法或除法可以代替加法和排除的程度.

决定最终创建概念证明,用于从无限输入集生成无限多个排列的命题,仅使用倾斜斜率,或仅使用索引作为数字,可能排列的前半部分加一.

// version 3, generate second half of permutations using indexes of first 
// half of permutations

function getNextLexicographicPermutation(arr) {

    for (var l = 1, i = k = arr.length; l < i ; k *= l++);

    function checkDigits(min, max, n) {
        var digits = 0;
        while (n) {
            d = (n % 10);
            n = n / 10 >> 0;
            if (d < min || d > max || (digits & (1 << d)))
                return false;
            else
                digits |= 1 << d;
        }
        return true;
    }

    var len = arr.length
    , idx = arr.map(function(_, index) {
        return index
    })
    , p = 9
    , min = 0
    , max = len - 1
    , last = Number(idx.slice().reverse().join(""))
    , curr = Number(idx.join(""))
    , res = []
    , diff = []
    , result = []
    , next;

    while (res.length < (k / 2) + 1) {
        next = (curr += p);
        if (checkDigits(min, max, next)) res[res.length] = next;      
        curr = next;
    };

    for (var i = 0; i < res.length; i++) {
      var item = res[i];
      item = String(item).split("").map(Number);
      item = (item.length < arr.length ? [0].concat(item) : item)
             .map(function(index) {
                return arr[index]
             }).filter(Boolean);
      result.push(item)
    }

    res.reduce(function(a, b) {
      diff.push(b - a);
      return b
    });

    for (var i = 0, curr = res[res.length - 1], n = diff.length - 2
        ; result.length < k;  i++, n--) {
          curr = curr + diff[n];
          result.push(
            String(curr).split("")
            .map(function(index) {
                return arr[index]
            })
          );
    }
    return result;
}
getNextLexicographicPermutation(arr);

算法开发的另一个最终步骤是给定一个任意.length输入,以便能够数学地计算索引,从而得到该集合的第n个排列的值; 通过使用乘法,除法,代数,三角函数或微积分的单一公式.

请在答案中包含可重复的基准.原因是我不能完全记住我如何得出Profilesat 的数字DevTools,尽管如果记得正确使用console.time(),console.timeEnd()以及console.profile()在使用的各个部分的开头和结尾.备份你的实验; 你永远不知道硬盘或操作系统是否或何时会崩溃.您通常可以从磁盘检索数据,但需要花费时间和精力.以同样的方式保存测试,您也可以保存算法版本,以便自我复制和重现其他人.原始测试的全部范围都丢失了.

在浏览器选项卡崩溃之前可以导出多少排列的测试的剩余部分只是从不同操作系统检索的注释

// 362880 876543210 876543219 
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];

如果准确地重新收集,何时"j"添加到数组中,铬的活动标签崩溃了.第一个数字是集合"a"到"i"的排列总数; 接下来的两个数字可能,但不确定,是今天组成的版本3之前的一个版本的两个测试的结果.

这是现在在stackoverflow.com上发布上述披露的另一个原因,为了保留算法的原理并对迄今为止完成的代码进行处理,减少一些灾难会破坏所有原始笔记和工作; 例如,连续几天醒来试图解释数字之间的模式和关系; 忽略了记录试图将算法移植到代码中的注释代码的所有特定测试模式; 或者@JaromandaX描述了环境"PEBCAK".

新鲜的眼睛可能从不同的角度看效率算法.

我们可以通过再现结果的曲线图,从上面的一些保留代码版本,例如console.time(),console.timeEnd(),performance.now()或涉及时间其他适当的测试,以完成的功能,它可以被再现.

// console.time("version N");
// getNextLexicographicPermutation(arr);
// console.timeEnd("version N");

var tests = [];

for (var i = 0; i < 10000; i++) {
  var from = window.performance.now();
  getNextLexicographicPermutation(arr);
  tests.push(window.performance.now() - from);
}

for (var i = 0, k = 0; i < tests.length; i++) {
  k += tests[i];
}

var avg = k/tests.length;

// version 1 `avg`: 0.2989265000001993
// version 2.0 `avg`: 0.8271295000007376
// version 2.1 `avg`: 0.17173000000003666
// version 3 `avg`: 0.12989749999987543

作为脚注,我会提到我使用算法的原理以最快的方式得到预期的结果,以便将所有大小为n的二进制字符串生成为布尔数组？同样,数字9在倾斜斜率内作为关键数字出现,并且也可以观察到赤纬的匹配角度.虽然没有对该问题所描述的特定形式的输入和结果进行进一步的测试和自动化.答案是关于忽略值的方法的可行性的概念证明,并且仅使用应用于单个数字初始数零的波状递增模式来导出集合的无限排列.

问题:

1. 如何提高算法的效率; 从计算上还是在数学上？

2. 我们可以同时创建倾斜度和倾斜度斜率的指标; 而不是在计算倾斜斜率后确定赤纬斜率？

   3. 索引之间是否存在数学关系或模式作为数字,例如,图1,图2或图3中的数字集,从任何四个值的输入派生而来,例如

      A B C D

   要么

   ["a", "b", "c", "d"]
   

   作者还没有认识到; 哪些可用于进一步减少目前实现的计算结果以获得结果？

Answer 1

TL; DR版本

不幸的是,提高此算法性能的唯一方法是摆脱它并使用更好的东西.

"真相"是否明显？(剧透警报:是的,他们是)

在你的长文中,我看到你发现的两个"真理":

1. 如果将数组索引编写为字符串,然后将这些字符串重新解释为两个连续排列的数字,则差值将乘以9

2. "斜率图"是对称的

不幸的是,这些事实都很明显,其中一个甚至都不是真的.

第一个事实是正确的,只要数组的长度小于10.如果它大于10,即一些索引被"映射"到2个字符,它就会停止为真.如果你知道9的可分性规则(在十进制系统中)显然是正确的:数字之和应该是9的乘数.显然,如果两个数字具有相同的数字,则它们具有相同的提醒模块9,因此它们的区别是9的乘法.此外,如果您在任何系统中解释您的字符串,其基数大于数组的长度,则差异将是base - 1相同原因的乘数.例如,让我们使用基于8的系统(列是:置换,置换索引,索引字符串,索引字符串从8基换算为十进制,差异):

abc 0 012 10  
acb 1 021 17   7
bac 2 102 66  49
bca 3 120 80  14
cab 4 201 129 49
cba 5 210 136  7

如果你总是使用大于数组长度的系统,那么这个事实是正确的(但你可能需要提出新的数字)

第二个陈述也是显而易见的,并且是"词典顺序"如何定义的直接后果.对于每个索引i,如果我对第一个i-th排列和最后一个排列的索引数组求和i-th,则总和将始终相同:所有值都等于数组长度的数组.例:

1. abc 012 - cba 210 => 012 + 210 = 222  
2. acb 021 - cab 201 => 021 + 201 = 222
3. bac 102 - bca 120 => 102 + 120 = 222

如果你考虑一系列负指数的排列,这很容易看出来[-N, -(N-1), ..., -1, 0].显然,i-th从这个数组开始的i-th排列与[0, 1, 2, ... N]从最终的排列相同,只是否定了符号.

其他问题

3. 索引之间是否存在数学关系或模式作为数字,例如,图1,图2或图3中的数字集,从任何四个值的输入派生而来,例如

是的,有.实际上,这正是为什么你在问题排列中没有递归函数调用的答案首先起作用的原因.但我怀疑有一种算法比该答案中提供的算法效率更高.实际上,该答案试图将所请求的排列的位置转换为变量基数值系统中的值,其中基数范围从1到数组的长度.(对于一个更广泛的变基数值系统的例子,考虑如何将毫秒转换为天 - 小时 - 分 - 秒 - 毫秒.你有效地使用数字系统,基数1000-60-60-24-unlimited.所以当你看到12345 days 8 hours 58 minutes 15 seconds 246 milliseconds你把它转换为毫秒,因为((((12345 * 24 + 8) * 60) + 58 * 60) + 15) * 1000 + 246你把那个符号表示为12345 (no base/unlimited) days 8 (24-base) hours 58 (60 base) minutes 15 (60 base) seconds 246 (1000-base) milliseconds).

通过排列,您可能需要执行两项不同的任务:

1. 生成i-th排列.您在SO答案中链接的算法相当有效.而且我怀疑还有更好的东西

2. 为给定的一个生成所有排列或排列流或下一个排列.这似乎是您尝试使用代码的那个.在这种情况下,分析给定排列的简单算法,找到排列未排序的第一个位置,并且开关+排序是否合理有效(这是拖延者似乎实现但我没有查看细节).我再次怀疑还有更好的东西.关于基于数字的算法不会更有效的主要障碍是因为它在一般情况下工作(即长度> = 10),你需要在大型基础中使用长算法进行除法,而这些操作不是O (1)了.

更新(回答评论)

我所声称的是,没有办法计算比直接计算排列序列更有效的数字序列.

我不同意这个主张.你能证明并证明这种说法吗？

不,我甚至不知道如何以正式方式陈述这种说法(如何定义不计算数字序列的算法类？).我仍然有一些证据支持这一点.

首先,你可能不是已知宇宙中最聪明的人,这是一个相对古老而众所周知的话题.因此,您发现一种比现有算法快得多的算法的可能性很低.事实上,没有人使用这种技术是一种反对你的证据.

另一点不那么随意:我在#2建议的用于生成序列中所有排列的算法实际上是相当有效的,因此很难被击败.

考虑一下找到下一个排列的步骤.首先,您需要找到订单不下降的末端的第一个位置.假设它会k.k找到它需要进行比较.然后你需要进行一次交换和排序.但是如果你有点聪明,你可能会注意到这里的"排序"可能会更快,因为列表已经排序(但顺序相反).因此,这里的排序只是找到k-th元素的位置.考虑到数组已排序,您可以使用O(log(k))复杂的二进制搜索.所以你需要k+1在内存中移动元素而不是k比较.这是一些代码:

// generates array of all permutatations of array of integers [0, 1, .., n-1]
function permutations(n) {
    // custom version that relies on a fact that all values are unique i.e. there will be no equality
    var binarySearch = function (tgt, arr, start, end) {
        // on small ranges direct loop might be more efficient than actual binary search
        var SMALL_THRESHOLD = 5;
        if (start - end < SMALL_THRESHOLD) {
            for (var i = start; i <= end; i++) {
                if (arr[i] > tgt)
                    return i;
            }
            throw new Error("Impossible");
        }
        else {
            var left = start;
            var right = end;
            while (left < right) {
                var middle = (left + right) >> 1; //safe /2
                var middleV = arr[middle];
                if (middleV < tgt) {
                    left = middle + 1;
                }
                else {
                    right = middle;
                }
            }

            return left;
        }
    };


    var state = [];
    var allPerms = [];
    var i, swapPos, swapTgtPos, half, tmp;
    for (i = 0; i < n; i++)
        state [i] = i

    //console.log(JSON.stringify(state));
    allPerms.push(state.slice()); // enfroce copy
    if (n > 1) {
        while (true) {
            for (swapPos = n - 2; swapPos >= 0; swapPos--) {
                if (state[swapPos] < state[swapPos + 1])
                    break;
            }

            if (swapPos < 0) // we reached the end
                break;

            // reverse end of the array
            half = (n - swapPos) >> 1; // safe /2
            for (i = 1; i < half + 1; i++) {
                //swap [swapPos + i] <-> [n - i]
                tmp = state[n - i];
                state[n - i] = state[swapPos + i];
                state[swapPos + i] = tmp;
            }

            // do the final swap
            swapTgtPos = binarySearch(state[swapPos], state, swapPos + 1, n - 1);
            tmp = state[swapTgtPos];
            state[swapTgtPos] = state[swapPos];
            state[swapPos] = tmp;
            //console.log(JSON.stringify(state));
            allPerms.push(state.slice()); // enfroce copy
        }
    }
    //console.log("n = " + n + " count = " + allPerms.length);
    return allPerms;
}

现在假设您使用基于数字的方法执行相同的操作,并且暂时假设您可以立即计算要为每个步骤添加的数字.那你现在用多少时间？因为你必须使用长算术,并且我们知道你的加法会改变的最高位是k-th,你需要至少执行k加法和k溢出的比较.当然,你仍然必须至少k写入内存.因此,为了比上面描述的"通常"算法更有效,您需要一种方法来计算一个k数字长数字(您将添加的数字),其时间少于在大小数组中执行二进制搜索k.这对我来说是一项非常艰巨的工作.例如,N-1仅使用相应的系数乘以9(或更确切地说)可能需要更长的时间来使用长算术.

那你还有什么机会呢？根本不要使用长的算术.在这种情况下,第一个明显的论点是,从数学上来说,比较小算法的性能N(这就是Big-O表示法用于算法复杂性的原因)是没有意义的.从纯数学的观点来看,为"小"的表现而斗争仍然是有意义的,但对于真实世界的情况而言,"大"的范围可以达到20个元素阵列的排列,这些元素仍然适合长期(64-位)整数.那么你可以通过不使用长算术获得什么？那么你的加法和乘法只需要一条CPU指令.但是你必须使用除法将你的号码拆分回数字,并且每一步都需要N划分和N检查(即比较).并且N总是大于k,往往更多.所以这对于性能改进来说也不是一个很好的途径.

总结:建议的算法是有效的,任何基于算术的算法在算术部分可能效率较低.

Answer 2

缺乏数学和英语技能使我很难详细说明这样的问题:-| 虽然我想玩一下排列，但我毕竟做了一些不那么偏离主题的事情。参见 TL;DR /sf/answers/3031161591/，我有同样的感觉，稍后我会尝试证明我的算法的有效性，我需要一点时间来思考。

var a = "aceg".split(""); 
do {
  console.log(a.join(""));
} while (a = next(a));

function next (a) {
  var i, c, head, next;
  var b = a.slice();
  var n = b.length;
  for (i = 1; i < n; i++) {
    if (b[n - i] > b[n - (i + 1)]) {
      head = n - (i + 1);
      next = n - i;
      for (i = next + 1; i < n; i++) {
        if (b[i] < b[next] && b[i] > b[head]) {
          next = i;
        }
      }
      c = b[head];
      b[head] = b[next];
      b[next] = c;
      return b.slice(0, head + 1).concat(
        b.slice(head + 1).sort()
      );
    }
  }
}