区块链技术博客
www.b2bchain.cn

如何直接获得序列的第n个排列的第i个元素(没有任何递归性)? – python程序员分享

本文介绍了如何直接获得序列的第n个排列的第i个元素(没有任何递归性)? – python程序员分享,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

假设我们有一个字符串“ ABCD”,我们想从字符串的第n个排列中检索第i个位置的字母。
在此示例中,我知道有factorial(4)= 24个排列,并且可以使用itertools.permutations轻松检索列表,它将得到以下信息:

[“ ABCD”,“ ABDC”,“ ACBD”,“ ACDB”,“ ADBC”,“ ADCB”,“ BACD”,“ BADC”,“ BCAD”,“ BCDA”,“ BDAC”,“ BDCA”,“ CABD”,“ CADB”,“ CBAD”,“ CBDA”,“ CDAB”,“ CDBA”,“ DABC”,“ DACB”,“ DBAC”,“ DBCA”,“ DCAB”,“ DCBA”]

因此,我要查找的函数f应该返回:

f(0,n)== [‘A’,’A’,’A’,’A’,’A’,’A’,’B’,’B’,’B’,’B’,’ B’,’B’,’C’,’C’,’C’,’C’,’C’,’C’,’D’,’D’,’D’,’D’,’D’ ,’D’] [n]
f(1,n)== [‘B’,’B’,’C’,’C’,’D’,’D’,’A’,’A’,’C’,’C’,’ D’,’D’,’A’,’A’,’B’,’B’,’D’,’D’,’A’,’A’,’B’,’B’,’C’ ,’C’] [n]
f(2,n)== [‘C’,’D’,’B’,’D’,’B’,’C’,’C’,’D’,’A’,’D’,’ A’,’C’,’B’,’D’,’A’,’D’,’A’,’B’,’B’,’C’,’A’,’C’,’A’ ,’B’] [n]
f(3,n)== [‘D’,’C’,’D’,’B’,’C’,’B’,’D’,’C’,’D’,’A’,’ C’,’A’,’D’,’B’,’D’,’A’,’B’,’A’,’C’,’B’,’C’,’A’,’B’ ,’A’] [n]

对于i == 0来说,这很容易,我们有f(0,n)==“ ABCD” [n // 6],但是当i增大时找到模式变得越来越复杂。
我完全不在乎排列的顺序,因此也许可以很容易地找到每个i值的通用模式…
我计划将其与一组256个元素和阶乘(256)排列一起使用,因此计算排列不是一个选择。
编辑:我已经有一个函数,但是它太慢了,我想知道是否可以通过使用例如按位运算的简单公式找到一些等效结果…
编辑2:由于@rici,这是当前最好的解决方案:

f = [factorial(i) for i in range(256)]      def _getElt(k, i):     """     Returns the <i>th element of the <k>th permutation of 0..255     """     table = list(range(256))      for j in range(255, 254-i, -1):         r, k = divmod(k, f[j])         perm[j], perm[r] = perm[r], perm[j]      return perm[255 - i] 

编辑3:这是使用多项式逼近来重新生成置换的另一种方法,因此问题的另一种表述可能是“如何为第n个置换重新生成多项式的第i个系数?”。
这是n = 4的n个置换多项式系数的列表(最后是从多项式系数重建的置换):

0 [0,1,2,3] [分数(0,1),分数(1,1),分数(0,1),分数(0,1)] [0,1,2,3]
1 [0,1,3,2] [分数(0,1),分数(-3,4),分数(5,2),分数(-2,3)] [0,1,3,2]
2 [0,2,1,3] [分数(0,1),分数(11,2),分数(-9,2),分数(1,1)] [0,2,1,3]
3 [0,2,3,1] [分数(0,1),分数(7,4),分数(1,2),分数(-1,3)] [0,2,3,1]
4 [0,3,1,2] [分数(0,1),分数(33,4),分数(-13,2),分数(4,3)] [0,3,1,2]
5 [0,3,2,1] [分数(0,1),分数(19,3),分数(-4,1),分数(2,3)] [0,3,2,1]
6 [1,0,2,3] [分数(1,1),分数(-15,4),分数(7,2),分数(-2,3)] [1,0,2,3]
7 [1,0,3,2] [分数(1,1),分数(-17,3),分数(6,1),分数(-4,3)] [1,0,3,2]
8 [1、2、0、3] [分数(1、1),分数(21、4),分数(-11、2),分数(4、3)] [1、2、0、3]
9 [1,2,3,0] [分数(1,1),分数(-1,3),分数(2,1),分数(-2,3)] [1,2,3,0]
10 [1,3,0,2] [分数(1,1),分数(31,4),分数(-15,2),分数(5,3)] [1,3,0,2]
11 [1,3,2,0] [分数(1,1),分数(17,4),分数(-5,2),分数(1,3)] [1,3,2,0]
12 [2,0,1,3] [分数(2,1),分数(-17,4),分数(5,2),分数(-1,3)] [2,0,1,3]
13 [2,0,3,1] [分数(2,1),分数(-31,4),分数(15,2),分数(-5,3)] [2,0,3,1]
14 [2,1,0,3] [分数(2,1),分数(1,3),分数(-2,1),分数(2,3)] [2,1,0,3]
15 [2,1,3,0] [分数(2,1),分数(-21,4),分数(11,2),分数(-4,3)] [2,1,3,0]
16 [2,3,0,1] [分数(2,1),分数(17,3),分数(-6,1),分数(4,3)] [2,3,0,1]
17 [2,3,1,0] [分数(2,1),分数(15,4),分数(-7,2),分数(2,3)] [2,3,1,0]
18 [3,0,1,2] [分数(3,1),分数(-19,3),分数(4,1),分数(-2,3)] [3,0,1,2]
19 [3,0,2,1] [分数(3,1),分数(-33,4),分数(13,2),分数(-4,3)] [3,0,2,1]
20 [3,1,0,2] [分数(3,1),分数(-7,4),分数(-1,2),分数(1,3)] [3,1,0,2]
21 [3,1,2,0] [分数(3,1),分数(-11,2),分数(9,2),分数(-1,1)] [3,1,2,0]
22 [3,2,0,1] [分数(3,1),分数(3,4),分数(-5,2),分数(2,3)] [3,2,0,1]
23 [3,2,1,0] [分数(3,1),分数(-1,1),分数(0,1),分数(0,1)] [3,2,1,0]

我们可以清楚地看到存在对称性:coefs [i] = [3-coefs [23-i] [0]] + [-c for coefs [23-i] [1:]]中的c探索,但我不知道这是有可能的。

参考方案

通过执行重复的欧几里得除法(商和余数,又称divmod)并跟踪选择的字母,可以找到第n个排列。然后,您可以从该排列中选择第i个字母。

假设S是初始字符串的副本,L该字符串的长度,而P排列数(L!)。 T将是逐步构建的nS排列。
示例:S = "ABCD"L = 4P = 24。让我们以n = 15为例。 T应该以"CBDA"结尾。

设置P = P/L。计算divmod(n, P),令q为商(n/P),使r为余数(n%P)。从q中删除​​第S个字母,并将其附加到T。设置n = r,减小L,然后重复直到L = 0
例:
1)P = 24/4 = 6q = 15/6 = 2r = 15%6 = 3S = "ABD"T = "C"n = r = 3L = 3
2)P = 6/3 = 2q = 3/2 = 1r = 3%2 = 1S = "AD"T = "CB"n = r = 1L = 2
3)P = 2/2 = 1q = 1/1 = 1r = 1%1 = 0S = "A"T = "CBD"n = r = 0L = 1
4)P = 1/1 = 1q = 0/1 = 0r = 0%1 = 0S = ""T = "CBDA"n = r = 0L = 0

由于只需要第i个字母,因此只要T的长度等于i+1,就可以停止并取最后一个字母。

我不会尝试用Python编写代码,因为自从接触Python以来已经太久了,但是here is a demo in C++。

我想使用Python 2和3版本。我已经读过有关conda环境的用法,但是不断向终端source (de)activate py27写入内容似乎不方便。如picture所示,如何使用命令选择内核版本? 参考方案 您在该图像中寻找的是Jupyter Notebook。您需要使用Jupyter和所需的python版本创建环境:conda create -n py…

我在具有以下基本结构(伪代码)的服务器上运行python脚本:for data_item in data_items: processed_result=process_data(data_item); #this takes time T0 upload_result_to_site(processed_result) #this takes time T…

在Python中,我正在使用uuid4()方法创建唯一的字符集。但是我找不到将其限制为10或8个字符的方法。有什么办法吗?uuid4()ffc69c1b-9d87-4c19-8dac-c09ca857e3fc谢谢。 参考方案 尝试:x = uuid4() str(x)[:8] 输出:"ffc69c1b" Is there a way to…

根据《 Google Python样式指南》,绝对不应(几乎)使用静态方法: 除非为了与 在现有库中定义的API。编写模块级功能 代替该建议背后的原因是什么?这是否仅适用于Google?还是在Python中使用静态方法还有其他(更一般的)缺点?尤其是,如果我想在将由该类的其他公共成员函数调用的类中实现实用程序功能,则最佳实践是什么?class Foo: ..…

Closed. This question is off-topic。它当前不接受答案。                                                                                                                                        …

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 如何直接获得序列的第n个排列的第i个元素(没有任何递归性)? – python程序员分享
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们