如何生成多个唯一或部分唯一的列表/向量（相同长度）？

问题描述 投票：0回答：1

我创建了以下函数，可以使用随机化生成 0 和 1 的列表（基本上是一个位串）。

import numpy as np

def generate_genome(length: int, max_individuals: int = 0) -> Genome:
    bits = None
    if max_individuals > 0:
        num_individuals = np.random.randint(1, max_individuals + 1)
        print(f'Will have maximum of {num_individuals} individuals')
        print('Controlled randomization')
        bits = np.full(length, 0)
        bits_flipped_ids = np.random.choice(range(0, length), size=num_individuals, replace=False)
        print(f'Following indices will be flipped: {sorted(bits_flipped_ids)}')
        np.put(a=bits, ind=bits_flipped_ids, v=1)
    else:
        print('Standard randomization')
        bits = np.random.choice([0, 1], size=length)

    genome = Genome(bits=bits.tolist())
    print(f'Genome bits: {genome.bits}')
    return genome

它支持两种模式：

  • without 
    max_individuals
    - 创建特定长度的位列表
  • with 
    max_individuals
    - 创建特定长度的位列表，但也确保 
    1
    的数量不超过 
    max_individuals
    。 
    1
    的位置是随机索引的（当然受列表允许长度的限制）

这是我正在研究的遗传算法的一部分。这将产生类似于以下的样本：

  • 没有 

    max_individuals

    generate_genome(10, 0)

[0 1 1 0 0 1 1 1 1 0]
[1 0 1 1 1 1 0 1 1 1]
[0 1 0 1 0 1 1 0 0 0]
[1 1 0 0 0 1 1 0 1 1]
[0 1 0 0 1 0 0 1 0 0]

  • 与 

    max_individuals

    generate_genome(10, 3)

[0 0 0 0 0 0 0 0 0 1] with bits flipped at [9]
[0 0 0 1 0 1 0 1 0 0] with bits flipped at [3 5 7]
[0 1 0 0 0 1 0 1 0 0] with bits flipped at [1 5 7]
[0 1 0 1 0 0 0 0 0 0] with bits flipped at [1 3]

我的问题是有可能生成相同的位列表。这种可能性随着 

length
和 
max_individuals
的减小而增加。我想控制它，看看它如何影响我的算法，所以我正在寻找一种有效的方法来使用我的函数创建一组唯一的位列表，甚至更好 - 一组位列表，其中唯一的数量列表可以通过参数控制。

更新：我根据评论设法简化了

generate_genome()
功能（谢谢！）。

def generate_genome(length: int, max_individuals: int = 0):
    # For the given length (number of bits) the maximum (where all are 1s)
    # is (2^length - 1). The numpy.arange() stops at (stop - 1)
    bits_all_possible = np.arange(2**length)
    # Shuffle to introduce randomness
    np.random.shuffle(bits_all_possible)
    
    if max_individuals > 0:
        bits_all_possible = np.array([b for b in bits_all_possible if np.bitwise_count(b) <= max_individuals])
        
    # Pick a random index between 0 and the length of all possible bit-fields
    bits_selected = np.random.randint(0, len(bits_all_possible))
    # Use the index to select the number
    bits_number = bits_all_possible[bits_selected]
    # Convert the number to a bit-field
    bits = [int(b) for b in bin(bits_number)[2:]]

    genome = Genome(bits=bits.tolist())
    print(f'Genome bits: {genome.bits}')
    return genome

但是，对于我来说这不是一个可行的解决方案，因为我们谈论的是编码而不是普通的旧二进制数。这意味着我可以拥有例如3121200 人。所有基因组都会有一个无法计算的最大值 

pow(N, length-1) = pow(2, 3121200-1) = ???
。

即使它有效，这种简化也不能解决使用 

generate_genome()
创建唯一的位字段列表的问题。直接的（尽管不确定效率如何）解决方案是创建一个列表并迭代地开始调用 
generate_genome()
。每次创建新的基因组时，我都可以检查它是否已存在于列表中。如果是，则将其丢弃，否则 - 添加。

目前我正在测试Python的

set
数据结构：

if unique_genomes:
    # Using a set allows ignoring newly inserted elements if these are already present
    genomes = set()
    genomes_len_old = 0
    for genome_counter in range(size):
        genome = Genome.generate_genome(genome_length, max_individuals)
        genomes_len_old = len(genomes)
        genomes.add(genome)
        # If the genome is already in the set, the number of elements in the set
        # will not change
        if genomes_len_old == len(genomes):
            # Reduce the counter by 1 and try again
            genome_counter -= 1
            continue
    genomes = list(genomes)

任何围绕尝试插入新基因组然后再次尝试插入新基因组（如果它不是唯一的）直到达到一定基因组总数的解决方案的问题是，它可能会导致寻找下一个基因组的永恒斗争。适合已经存在的基因库，因为每次调用 

generate_genome()
时，都会有未知的可能性创建一个已经存在的基因组，因此最坏的情况我可能会创建一个无限循环。过去我添加了一个终止标准，即在打破之前应该有多少次尝试。在这里，这不是一个选择。

python algorithm random
1个回答
0
投票

令 

m
为位数，
k
为您要生成的位串数量，
r
为每个位串中 1 的最大数量（您的 
max_individuals
参数）。

需要考虑的一些情况：

  1. 1 位数没有最大限制。在这种情况下，问题归结为选择长度为 

    k
    的唯一比特串。您可以通过对从 0 到 
    m
    的 
    k
    随机整数进行采样来实现此目的。这是非常有效地做到这一点的算法：
    2^m - 1
    

    

    2. 即使对于非常大的 
import random
import numpy as np

def int2bs(x, m):
    """ Convert an integer to a bitstring of length m """
    # round m up to a multiple of 8
    mbytes = (m + 7) & ~7
    xbytes = x.to_bytes(mbytes >> 3, "big")
    res = np.unpackbits(np.frombuffer(xbytes, np.uint8))
    return res[mbytes - m:]

def rand_bitstrings(m, k):
    n = 2 ** m
    if k > n:
        raise ValueError(f"Can't choose more than {n} bitstrings")

    if k >= n // 3 or n <= 32:
        # Selecting a large fraction of the possible bitstrings: faster to shuffle the whole list and take a subset
        all_bs = list(range(n))
        random.shuffle(all_bs)
        res = all_bs[:k]
    else:
        # Rejection sampling with a guaranteed success rate of >= 2/3 per trial
        seen = set()
        res = []
        while len(res) < k:
            bs = random.getrandbits(m)
            while bs in seen:
                bs = random.getrandbits(m)
            seen.add(bs)
            res.append(bs)

    # Convert integers to bitstrings
    return [int2bs(x, m) for x in res]

 值，这也相当快；对于 
m
，这在我的机器上需要 19 毫秒。


    生成
  1. m = 3121200, k = 3
    长度的比特串，其中
    恰好
    m1位。在这种情况下，我们可以执行以下操作：
    r
    

    然后，我们可以将返回的
    return tuple(random.sample([0, 1], m, counts=[m-r, r]))

    放入一个集合中以检查是否有重复。
    

    2. 生成最多 
  2. tuple
     1 位的比特串。我不知道有什么好方法可以有效地实现一般 
    r
     以及所有位串之间的均匀分布。然而，这里有一种方法可以有效地生成长度为 
    r
     且最多有 
    m
     1 位的随机位串，尽管偏向于具有大约 r/2 1 位的位串：
    r
    

    与 #2 一样，您可以将返回的元组放入一个集合中以检查重复项。
    

    

    

    3. 对于#2和#3，为了避免出现较长的拒绝采样延迟的可能性，可以检查可能的输出总数是否小于3*k；如果是，只需打乱所有可能性并输出第一个 
return tuple(random.sample([0, 1], m, counts=[m, r]))

 （如第一个答案中所做的那样）。
    

	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.