时间戳

首页 > 解决方案 > 通过规则生成新元组

python - 通过规则生成新元组

问题描述

我试图通过 n 个整数的不同排列，并根据以下规则为每个整数生成一个新的排列：

例如，查看 (1,2,3) 的排列： (2,3,1) 将生成 (3,1,2)，因为第一个元组中 2 的索引是 1 所以 2 替换 1，索引 3 是2 所以 3 替换 2，1 的索引是 3 所以 1 替换 3

我想知道最有效的方法是什么？

我已经使用 itertools 中的 permutations 函数启动了该函数：

# Define a function with the input of a list of the permutations/n-tuples L e.g. [1,2,3]

from itertools import *
def GeneratePerm(L):
  perm=list(permutations(L))
  for p in perm:
      for element in p:
          index=p.index(element)
          index=index+1
          if element==index:
              new_tup=p.index(element)
          print('new_tup:',new_tup)

我真的不确定从这里去哪里，所以任何回复都将不胜感激！谢谢！

标签： pythonpython-3.xtuples

解决方案

由于 Python 的元组索引是从零开始的，因此考虑 的排列（(0, 1, 2)这很常见）而不是 的排列会更简单(1, 2, 3)。对于这个问题，使用列表而不是元组也会更简单。但是这里有一些代码可以为给定的基于 1 的排列找到基于 1 的“逆排列”。

p_example = (2, 3, 1)  # to (3, 1, 2)

def inv_1_based_permutation(p):
    result = [0] * len(p)
    for ndx, val in enumerate(p):
        result[val - 1] = ndx + 1
    return tuple(result)

print(inv_1_based_permutation(p_example))

请注意，- 1and+ 1是由于排列是从一开始的，并且例程中的最后一行从列表转换为元组。中间列表是必要的，因为该算法通过以与结果中使用的顺序不同的顺序修改序列来工作（顺序基于输入参数）。该例程的时间复杂度是O(n)排列n的长度。您的代码是O(n^2)since index()is O(n)，并且您为排列的每个成员调用一次。

推荐阅读