快速放置拼图的方法 - python

我正在编写代码来解决以下难题。

考虑长度为n的二进制矢量,该矢量最初为零。您选择一个向量位并将其设置为1。现在,将启动一个过程,该过程将距离任意1位最大距离的位设置为$ 1 $(如果有多个,则任意选择最远的位)。重复发生这种情况的规则是两个1位不能相邻。当没有更多空间放置1位时,它将终止。目标是放置初始的1位,以便在终止时将尽可能多的位设置为1。

假设n =2。那么无论我们在何处设置该位,最终都只设置了一位。

对于n = 3,如果我们设置第一个位,则最后得到101。但是,如果我们设置中间位,则得到010,这不是最佳的。

对于n = 4,无论我们设置的哪个位,我们最终都设置两个。

对于n = 5,设置第一个给我们10101,最后设置三个位。

对于n = 7,我们需要将第三位设置为1010101。

我已经编写了代码来找到最佳值,但是它不能很好地缩放到大n。我的代码在n = 1000左右开始变慢,但是我想在n左右解决一百万个问题。

#!/usr/bin/python
from __future__ import division
from math import *

def findloc(v):
    count = 0
    maxcount = 0
    id = -1
    for i in xrange(n):
        if (v[i] == 0):
            count += 1
        if (v[i] == 1):
            if (count > maxcount):
                maxcount = count
                id = i
            count = 0

#Deal with vector ending in 0s
    if (2*count >= maxcount and count >= v.index(1) and count >1):
        return n-1
#Deal with vector starting in 0s
    if (2*v.index(1) >= maxcount and v.index(1) > 1):
        return 0
    if (maxcount <=2):
        return -1    
    return id-int(ceil(maxcount/2))


def addbits(v):
    id = findloc(v)
    if (id == -1):
        return v
    v[id] = 1
    return addbits(v)

#Set vector length
n=21    
max = 0
for i in xrange(n):
    v = [0]*n
    v[i] = 1
    v = addbits(v)
    score = sum([1 for j in xrange(n) if v[j] ==1])
#        print i, sum([1 for j in xrange(n) if v[j] ==1]), v
    if (score > max):
        max = score       
print max

参考方案

最新答案(O(log n)复杂度)

如果我们相信由templatetypedef和Aleksi Torhamo提出的猜想(更新:本文末尾的证明),那么可以使用count(n)(或O(log n)如果假设对数和移位为):

蟒蛇:

from math import log

def count(n): # The count, using position k conjectured by templatetypedef
    k = p(n-1)+1
    count_left = k/2
    count_right = f(n-k+1)
    return count_left + count_right

def f(n): # The f function calculated using Aleksi Torhamo conjecture
    return max(p(n-1)/2 + 1, n-p(n-1))

def p(n): # The largest power of 2 not exceeding n
    return 1 << int(log(n,2)) if n > 0 else 0

C ++:

int log(int n){ // Integer logarithm, by counting the number of leading 0
    return 31-__builtin_clz(n);
}

int p(int n){ // The largest power of 2 not exceeding n
    if(n==0) return 0;
    return 1<<log(n);
}

int f(int n){ // The f function calculated using Aleksi Torhamo conjecture
    int val0 = p(n-1);
    int val1 = val0/2+1;
    int val2 = n-val0;
    return val1>val2 ? val1 : val2;
}

int count(int n){ // The count, using position k conjectured by templatetypedef
    int k = p(n-1)+1;
    int count_left = k/2;
    int count_right = f(n-k+1);
    return count_left + count_right;
}

此代码可以在没有时间的情况下正确计算O(1)的结果(甚至在Python中甚至是O(1)!)。

我已经使用n=100,000,000的各种值测试了代码(使用我的n=1e24解决方案作为标准,请参见下面的“旧答案”部分),它们似乎仍然正确。

该代码依赖templatetypedef和Aleksi Torhamo2的两个推测。有人想证明那些吗? = D(更新2:已验证)

1没有时间,我的意思是几乎立即
2 Aleksi Torhamo对n函数的猜想已通过O(n)的经验证明

旧答案(O(n)复杂度)

我可以使用Python 2.7在1.358s(在我的iMac中)中返回f的计数(结果为n<=100,000,000)。更新:在C ++中,n=1,000,000为0.198s。 =)

这是我的想法,它实现了475712时间的复杂性。

算法

n=10,000,000的定义

定义O(n)为将在长度为f(n)的位向量上设置的位数,并假设设置了第一位和最后一位(f(n)除外,其中仅设置了第一位或最后一位)。因此,我们知道n的一些值如下:

f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 2
f(5) = 3

请注意,这与我们要查找的值不同,因为根据n=2的计算,初始位可能不在第一位或最后一位。例如,我们用f(n)而不是4。

请注意,使用递归关系可以相当有效地计算出此值(摊销f(n)以计算f(7)=3直至O(n)的所有值):

f(2n) = f(n)+f(n+1)-1
f(2n+1) = 2*f(n+1)-1

对于f,因为除n之外,规则后的下一位将是中间位。然后,我们可以将位向量分为两个部分,每个部分彼此独立,因此可以计算使用n>=5设置的位数,如下所示:

n=11              n=13
10000100001       1000001000001
<---->            <----->
 f(6)<---->        f(7) <----->
      f(6)               f(7)

n=12              n=14
100001000001      10000010000001
<---->            <----->
 f(6)<----->       f(7) <------>
      f(7)                f(8)

we have the -1 in the formula to exclude the double count of the middle bit.

Now we are ready to count the solution of original problem.

Definition of g(n,i)

Define g(n,i) as the number of bits that will be set on bitvector of length n, following the rules in the problem, where the initial bit is at the i-th bit (1-based). Note that by symmetry the initial bit can be anywhere from the first bit up to the ceil(n/2)-th bit. And for those cases, note that the first bit will be set before any bit in between the first and the initial, and so is the case for the last bit. Therefore the number of bit set in the first partition and the second partition is f(i) and f(n+1-i) respectively.

So the value of g(n,i) can be calculated as:

g(n,i) = f(i) + f(n+1-i) - 1

在计算n=1,2,3,4时遵循此想法。

现在,要计算最终结果是微不足道的。

f( floor(n/2) ) + f( ceil(n/2) ) - 1的定义

f(n)定义为原始问题中要查找的计数。然后,我们可以取所有可能的最大值g(n),即初始位的位置:

g(n) = maxi=1..ceil(n/2)(f(i) + f(n+1-i) - 1)

Python code:

import time
mem_f = [0,1,1,2,2]
mem_f.extend([-1]*(10**7)) # This will take around 40MB of memory
def f(n):
    global mem_f
    if mem_f[n]>-1:
        return mem_f[n]
    if n%2==1:
        mem_f[n] = 2*f((n+1)/2)-1
        return mem_f[n]
    else:
        half = n/2
        mem_f[n] = f(half)+f(half+1)-1
        return mem_f[n]

def g(n):
    return max(f(i)+f(n+1-i)-1 for i in range(1,(n+1)/2 + 1))

def main():
    while True:
        n = input('Enter n (1 <= n <= 10,000,000; 0 to stop): ')
        if n==0: break
        start_time = time.time()
        print 'g(%d) = %d, in %.3fs' % (n, g(n), time.time()-start_time)

if __name__=='__main__':
    main()

复杂度分析

现在,有趣的是,使用上述方法计算g(n)的复杂度是多少?

首先应注意,我们迭代了ig(n)值,即初始位的位置。在每次迭代中,我们分别调用n/2i。幼稚的分析将导致f(i),但是实际上我们在f(n+1-i)上使用了记忆,因此它要快得多,因为O(n * O(f(n)))的每个值最多只能计算一次。因此,复杂度实际上是通过计算f的所有值所需的时间来增加的,而该值应为f(i)

那么初始化f(n)的复杂性是什么?

我们可以假设我们先计算O(n + f(n))的每个值,然后再计算f(n)。注意,由于递归关系和备忘录,生成f(n)的整个值需要g(n)的时间。下一次调用f(n)将花费O(n)时间。

因此,总体复杂度为f(n),正如我在iMac中针对O(1)O(n+n) = O(n)的运行时间所证明的:

> python max_vec_bit.py
Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000
g(1000000) = 475712, in 1.358s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0
>
> <restarted the program to remove the effect of memoization>
>
> python max_vec_bit.py
Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000
g(10000000) = 4757120, in 13.484s
Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231
g(6745231) = 3145729, in 3.072s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0

And as a by-product of memoization, the calculation of lesser value of n will be much faster after the first call to large n, as you can also see in the sample run. And with language better suited for number crunching such as C++, you might get significantly faster running time

I hope this helps. =)

The code using C++, for performance improvement

The result in C++ is about 68x faster (measured by clock()):

> ./a.out
Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000
g(1000000) = 475712, in 0.020s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0
>
> <restarted the program to remove the effect of memoization>
>
> ./a.out
Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000
g(10000000) = 4757120, in 0.198s
Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231
g(6745231) = 3145729, in 0.047s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0

Code in C++:

#include <cstdio>
#include <cstring>
#include <ctime>

int mem_f[10000001];
int f(int n){
    if(mem_f[n]>-1)
        return mem_f[n];
    if(n%2==1){
        mem_f[n] = 2*f((n+1)/2)-1;
        return mem_f[n];
    } else {
        int half = n/2;
        mem_f[n] = f(half)+f(half+1)-1;
        return mem_f[n];
    }
}

int g(int n){
    int result = 0;
    for(int i=1; i<=(n+1)/2; i++){
        int cnt = f(i)+f(n+1-i)-1;
        result = (cnt > result ? cnt : result);
    }
    return result;
}

int main(){
    memset(mem_f,-1,sizeof(mem_f));
    mem_f[0] = 0;
    mem_f[1] = mem_f[2] = 1;
    mem_f[3] = mem_f[4] = 2;
    clock_t start, end;
    while(true){
        int n;
        printf("Enter n (1 <= n <= 10,000,000; 0 to stop): ");
        scanf("%d",&n);
        if(n==0) break;
        start = clock();
        int result = g(n);
        end = clock();
        printf("g(%d) = %d, in %.3fs\n",n,result,((double)(end-start))/CLOCKS_PER_SEC);
    }
}

证明

请注意,为了使这个答案(已经很长了)很简单,我跳过了证明中的一些步骤

Aleksi Torhamo关于n=1,000,000值的猜想

对于“ n> = 1”,请证明:
对于k = 1,2,...,2n-1 ...(1),f(2n + k)= 2n-1 + 1
对于k = 2n-1 + 1,...,2n ...(2),f(2n + k)= k
给定f(0)= f(1)= f(2)= 1

通过考虑以下四种情况,可以通过对递归关系进行归纳来轻松证明上述结果:

情况1:(1)连n=10,000,000
情况2:(1)为奇数f
情况3:(2)连k
情况4:(2)为奇数k

假设我们有证明n的四种情况。现在考虑n + 1。
情况1:
f(2n + 1 + 2i)= f(2n + i)+ f(2n + i + 1)-1,对于i = 1,…,2n-1
= 2n-1 + 1 + 2n-1 + 1-1
= 2n + 1

情况2:
f(2n + 1 + 2i + 1)= 2 * f(2n + i + 1)-1,对于i = 0,...,2n-1-1
= 2 *(2n-1 + 1)-1
= 2n + 1

情况3:
f(2n + 1 + 2i)= f(2n + i)+ f(2n + i + 1)-1,对于i = 2n-1 + 1,…,2n
= i +(i + 1)-1
= 2i

情况4:
f(2n + 1 + 2i + 1)= 2 * f(2n + i + 1)-1,对于i = 2n-1 + 1,…,2n-1
= 2 *(i + 1)-1
= 2i + 1

因此通过归纳证明了这一猜想。

templatetypedef在最佳位置上的猜想

对于n> = 1和k = 1,…,2n,证明g(2n + k)= g(2n + k,2n + 1)
也就是说,证明将第一个比特放在第2n + 1个位置上可以设置的最大比特数。

证据:

首先,我们有
g(2n + k,2n + 1)= f(2n + 1)+ f(k-1)-1

接下来,通过f的公式,我们具有以下等式:
对于i = -2n-1,...,-1,f(2n + 1-i)= f(2n + 1)
f(2n + 1-i)= f(2n + 1)-i,对于i = 1,…,2n-2-1
f(2n + 1-i)= f(2n + 1)-2n-2,对于i = 2n-2,…,2n-1

还有以下不平等:
f(k-1 + i)<= f(k-1),对于i = -2n-1,…,-1
f(k-1 + i)<= f(k-1)+ i,对于i = 1,…,2n-2-1
f(k-1 + i)<= f(k-1)+ 2n-2,对于i = 2n-2,…,2n-1

因此,我们有:
f(2n + 1-i)+ f(k-1 + i)<= f(2n + 1)+ f(k-1),对于i = -2n-1,...,2n-1

现在,请注意我们有:
g(2n + k)= maxi = 1..ceil(2n-1 + 1-k / 2)(f(i)+ f(2n + k + 1-i)-1)
<= f(2n + 1)+ f(k-1)-1
= g(2n + k,2n + 1)

因此,这一猜想得到了证明。

如何使用BeautifulSoup在<tr>中捕获特定的<td> - python

尝试从nyc Wiki页面中的高中列表中获取所有高中名称。我已经写了足够多的脚本,可以让我获取包含在高中,学业和入学条件列表的表的<tr>标记中的所有信息-但是我如何才能缩小到我认为的范围内在td[0]内休息(会弹出KeyError)-只是学校的名称?到目前为止我写的代码:from bs4 import BeautifulSoup from ur…

Python numpy数据指针地址无需更改即可更改 - python

编辑经过一些摆弄之后,到目前为止,我已经隔离了以下状态:一维数组在直接输入变量时提供两个不同的地址,而在使用print()时仅提供一个地址2D数组(或矩阵)在直接输入变量时提供三个不同的地址,在使用print()时提供两个地址3D数组在直接输入变量时提供两个不同的地址,而在使用print()时仅给出一个(显然与一维数组相同)像这样:>>> …

Python Pandas导出数据 - python

我正在使用python pandas处理一些数据。我已使用以下代码将数据导出到excel文件。writer = pd.ExcelWriter('Data.xlsx'); wrong_data.to_excel(writer,"Names which are wrong", index = False); writer.…

Python ElementTree:在循环中替换元素 - python

我正在尝试创建一个脚本,该脚本循环创建一个xml文件,并为两个元素增加值。 (使用netaddr的IP地址,以及递增的tag / member元素,tag01-tag10)from netaddr import IPNetwork import xml.dom.minidom import lxml.etree as etree import xml.etr…

在节点有数据的地方绘制图形 - python

我有一个包含一些复杂数据的有向图。我想绘制此图并将每个节点表示为一个表。有没有办法做到这一点?我发现的所有绘图示例都只有一个标签或一些简单地绘制到节点中的示例。仅供参考:我目前正在使用networkx 参考方案 使用graphviz时,标签可以代表更复杂的东西,例如表格。Graphviz提供两种变体:Record based nodes基于记录的节点提供了一…