计数单个交叉的可能性 [英] Count possibilites for single crossovers

问题描述

我有以下问题.在我的代码中 我有大小为L的数组.所有数组的条目均为0或1.让我们以L = 3为例.三个可能的数组是(1,1,1)，(1,0,0)和(0,1,1).现在，我想知道通过(1,0,0)和(0,1,1)形成(1,1,1)可以进行多少次单交叉.答案将是一个.对于(1,0,1)和(0,1,0)形成(1,1,1)的答案将为0，因为我需要两个分频器.我正在寻找一种针对一般L执行此操作的算法(L通常不大于9).到目前为止，我还没有任何想法，这就是为什么我将这个问题发布给她，但是如果有的话我会进行编辑.希望你能帮助我:)

I have the following problem. In my code I have arrays of size L. The entries are either 0 or 1 for all arrays. Lets set L=3 for an example. Three possible arrays are (1,1,1), (1,0,0) and (0,1,1). Now I want to know how many single crossovers are possible with (1,0,0) and (0,1,1) to form (1,1,1). The answer would be one. For (1,0,1) and (0,1,0) to form (1,1,1) the answer would be 0, because I would need two crossovers. I am looking for an algorithm which does this for general L. (L is usually not larger than 9). So far I don't have any idea and that is why I have post this problem her but I will make an edit if I got one. Hope you can help me :)

结果当然不仅可以是0或1，而且可以大于1. 示例:(1,1,0,0)和(0,0,0,0)形成(0,0,0,0)的结果将为2.(我只能获取第一个数组的最后一个条目或第一个数组的最后2个条目)

The outcome can be of course not only 0 or 1 but also greater than 1. Example: (1,1,0,0) and (0,0,0,0) to form (0,0,0,0) the outcome would be 2. (I can only take the last entry of the first array or the last 2 entries of the first array)

我的意思是通过一次交叉，我可以采用第一个序列的左侧/右侧和第二个序列的右侧/左侧来形成给定的第三个序列. (1,1,0,0)和(0,0,0,0)组成(0,0,0,0)-> 0,0) + (0,0,或0) + (0,0,0,

Edit 2: By single crossover I mean, that I can take the left/right side of the first sequence and the right/left side of the second sequence to form the given third sequence. (1,1,0,0) and (0,0,0,0) to form (0,0,0,0) --> 0,0) + (0,0, or 0) + (0,0,0,

推荐答案

解释问题的另一种方法是计算

Another way of interpreting the problem is as calculating the Hamming Distance. Here is a snippet to create a dictionary of all pairs of each Hamming Distance/crossovers.

from itertools import combinations

tuples = [(0, 0, 1), (1, 0, 0), (1, 0, 1)]
crossovers = {k: [] for k in range(len(tuples[0]))}
for a, b in combinations(tuples, r=2):
    num_crossovers = sum(el1 != el2 for el1, el2 in zip(a, b))
    crossovers[num_crossovers].append((a, b))

执行分频后将如下所示

{0: [],
 1: [((0, 0, 1), (1, 0, 1)), ((1, 0, 0), (1, 0, 1))],
 2: [((0, 0, 1), (1, 0, 0))]}

我想念您使用的是numpy数组而不是元组，您可以这样做

I missed that you were using numpy arrays instead of tuples, you could do

arrays = np.array([[0, 0, 1], [1, 0, 0], [1, 0, 1]])
crossovers = {k: [] for k in range(arrays[0].size)}
for a, b in combinations(arrays, r=2):
    num_crossovers = sum(np.abs(a - b))
    crossovers[num_crossovers].append((a, b))

这篇关于计数单个交叉的可能性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！