排列,创建限制

2024-03-28 10:23:24 发布

您现在位置:Python中文网/ 问答频道 /正文

我使用的是Python,还有Pandas和Numpy,不过这个问题看起来更像是一个更通用的算法设计问题。在

我有一个元素列表(实际上是一个数组),我想生成该列表的排列。但是,某些项目不允许位于列表中的某些位置。我想生成一个服从这些限制的排列。什么是有效的方法?在

我的实际用途是一个Pandas数据帧,有两列X和{}。X和{}都有相同的数字,顺序不同。数字不是唯一的。同一行中的XY中没有数字(即没有数字与自身匹配)。我想置换Y,同时保持没有数字与自身匹配的限制。我在Y上调用了Numpy的permute,但是大约有1%的结果行是X==Y。在

编辑示例:

import pandas as pd
import numpy as np

data = [[1,2],
        [1,4],
        [4,2],
        [2,3]]

df = pd.DataFrame(columns=['X', 'Y'],
              data=data)


df_permuted = df.copy()

df_permuted.Y = np.random.permutation(df.Y)

print(df.X==df.Y)
#0    False
#1    False
#2    False
#3    False
#dtype: bool

print(df_permuted.X==df_permuted.Y)
#0    False
#1    False
#2    False
#3     True
#dtype: bool

编辑: 明显的算法太慢/无法扩展,是:

^{pr2}$

在我们的熊猫例子中,这将是:

from numpy.random import choice
for i in df.index:
    other_rows = df[(df.ix[i].X != df.Y) * (df.ix[i].Y != df.X)]
    selected_row = choice(other_rows.index)
    original_Y = df.ix[i].Y
    df.ix[i].Y = df.ix[selected_row].Y
    df.ix[selected_row].Y = original_Y
print(df.X==df.Y)
#0    False
#1    False
#2    False
#3    False
#dtype: bool

问题是这太慢了,根本没有并行化。有没有一种方法可以并行化?我想答案是“不”,因为在一行进行的交换会影响到下一行的有效“其他人”。在

缩放感编辑: 大约1.4*10^7行,X中有2*10^6个唯一值,Y中有一个相似的数。需要生成大约10^3个独立的置换。实际上,我把一组行单独排列,有些组很小(例如10行),但很多组相当大(10^5)。这买了一点帮助,但最后还是有很多争吵!只需在10^7行上运行一个简单的np.random.permutation大约需要7秒,这就足够了。运行上面的限制排列算法(为了提高速度,用numpy而不是pandas实现)只需7秒,只需10^3行。呃!在


Tags: importnumpy算法false编辑df列表data
2条回答

我希望我没有提出一个对你的例子过于具体的解决方案。但是,如果可行,您可以创建每个排列,然后删除不符合您的条件的排列。然后您可以直接使用该样本,也可以从结果排列中随机抽取样本。在

下面的代码是受上面的示例启发的。我意识到我使用的起始假设略有不同:

df = pd.DataFrame( list(itertools.product([1,2,3,4], [1,2,3,4])), columns = ['X','Y'])
print df


    X  Y
0   1  1
1   1  2
2   1  3
3   1  4
4   2  1
5   2  2
6   2  3
7   2  4
8   3  1
9   3  2
10  3  3
11  3  4
12  4  1
13  4  2
14  4  3
15  4  4

然后设置您感兴趣的条件:

^{pr2}$

编辑: 我会把上面所有的组合垃圾留在那里,因为别人可能会觉得有用。但在评论中聊天后,我想我有一个可能的解决办法。在

您似乎可以进行排列,然后将排列的数据帧分成两个子集:

  1. 不符合条件的数据(即X==Y)
  2. 符合条件的数据(X!=Y)

然后我们可以取第一个子集,再简单地置换它。子集1应该比子集2小得多。我们只是递归地这样做,创建一组符合条件的记录应该非常容易和快速。在

当然,我们必须处理只有一行匹配的情况。在

我实施了一个示例解决方案:

设置一些与实际数据大小相似的播放数据:

np.random.seed(3)
n=14000000
df = pd.DataFrame({'X' : np.random.randint(2000000, size=n), 
                   'Y' : np.random.randint(2000000, size=n)})

示例数据将以一些重复的行开始,但这没关系。让我们创建shuffle函数:

def permuteDataFrame(inDf):
    permutedDf = pd.DataFrame({'X' : np.random.permutation(inDf.X), 
                               'Y' : np.random.permutation(inDf.Y)})
    # check for dupes
    clash = permutedDf[permutedDf.X == permutedDf.Y] 
    if clash.shape[0] > 1: #repermuting can't work if only one row has a match
        clash = permutedDf[permutedDf.X == permutedDf.Y].copy()
        noclash = permutedDf[permutedDf.X != permutedDf.Y].copy()
        # recursion FTW: run the clashes back through this algo
        clash = permuteDataFrame(clash)
        permutedDf = pd.concat([clash, noclash ])
    if clash.shape[0] == 1: # handle the single match problem
        # solving the single match by grabbing the single match plus a random other record and permuting
        # get the vector of bools that indicate matches
        clashIndex = permutedDf.X == permutedDf.Y
        # randomly make another one True
        ilocToSwap = np.random.randint(permutedDf.shape[0]) # random record location to swap
        indexOfClashes.iloc[ilocToSwap] = True
        clash = permutedDf[indexOfClashes]
        # recursion FTW: run the clashes back through this algo
        clash = permuteDataFrame(clash)
        permutedDf = pd.concat([clash, noclash ])
    return permutedDf

在我的Mac电脑上,一个简单的排列需要5.3秒。新的permuteDataFrame()函数需要5.8秒。即使在你的机器上花了8秒,也能在2.2小时内得到1000个。那可能有用。在

为什么不直接做你正在做的事情(永久性Y),但最后检查一下,确保没有匹配项:

if (df.X == df.Y).any():
    reject_dataframe()

相关问题 更多 >