将整数表示为一系列乘法器

使现代化

我忍不住要为第一个问题想出我自己的解决方案,尽管它不做压缩。下面是一个使用第三方分解算法pyecm的Python解决方案。

这个解决方案可能比叶夫根尼的方案效率高几个数量级。计算y的合理值需要几秒钟而不是几小时,甚至几周/年。对于x=2^32-1和y=256,我的核心duo 1.2 ghz需要1.68秒。

>>> import time
>>> def test():
...     before = time.time()
...     print factor(2**32-1, 256)
...     print time.time()-before
...
>>> test()
[254, 232, 215, 113, 3, 15]
1.68499994278
>>> 254*232*215*113*3+15
4294967295L

def factor(x, y):
    # y should be smaller than x. If x=y then {y, 1, 0} is the best solution
    assert(x > y)

    best_output = []

    # try all possible remainders from 0 to y 
    for remainder in xrange(y+1):
        output = []
        composite = x - remainder
        factors = getFactors(composite)

        # check if any factor is larger than y
        bad_remainder = False
        for n in factors.iterkeys():
            if n > y: 
                bad_remainder = True
                break
        if bad_remainder: continue

        # make the best factors
        while True:
            results = largestFactors(factors, y)
            if results == None: break
            output += [results[0]]
            factors = results[1]

        # store the best output
        output = output + [remainder]
        if len(best_output) == 0 or len(output) < len(best_output):
            best_output = output

    return best_output

# Heuristic
# The bigger the number the better. 8 is more compact than 2,2,2 etc...

# Find the most factors you can have below or equal to y
# output the number and unused factors that can be reinserted in this function
def largestFactors(factors, y):
    assert(y > 1)
    # iterate from y to 2 and see if the factors are present.
    for i in xrange(y, 1, -1):
        try_another_number = False
        factors_below_y = getFactors(i)
        for number, copies in factors_below_y.iteritems():
            if number in factors:
                if factors[number] < copies:
                    try_another_number = True
                    continue # not enough factors
            else:
                try_another_number = True
                continue # a factor is not present

        # Do we want to try another number, or was a solution found?
        if try_another_number == True:
            continue
        else:
            output = 1
            for number, copies in factors_below_y.items():
                remaining = factors[number] - copies
                if remaining > 0:
                    factors[number] = remaining
                else:
                    del factors[number]
                output *= number ** copies

            return (output, factors)

    return None # failed




# Find prime factors. You can use any formula you want for this.
# I am using elliptic curve factorization from http://sourceforge.net/projects/pyecm
import pyecm, collections, copy

getFactors_cache = {}
def getFactors(n):
    assert(n != 0)
    # attempt to retrieve from cache. Returns a copy
    try:
        return copy.copy(getFactors_cache[n])
    except KeyError:
        pass

    output = collections.defaultdict(int)
    for factor in pyecm.factors(n, False, True, 10, 1):
        output[factor] += 1

    # cache result
    getFactors_cache[n] = output

    return copy.copy(output)

对第一个问题的答复

你说你想压缩数字,但从你的例子来看,那些序列比未分解的数字要长。如果没有您遗漏的系统的更多细节(序列概率/是否有可编程客户端?),则无法压缩这些数字。你能详细说明一下吗?

这是一个数学解释,解释了为什么当前对问题第一部分的回答永远无法解决第二个问题。这与背包问题无关。

这是香农的熵算法。它告诉你需要代表序列{x0,x1,x2,…,xn-1,xn}的理论最小位数,其中p(Xi)是看到令牌席席的概率。

当我们将它插入香农算法时,它将告诉我们表示流所需的最小位数。

import math

def entropy():
    num = 2**32
    probability = 1./num
    return -(num) * probability * math.log(probability, 2)
    # the (num) * probability cancels out

毫不奇怪,熵是32。 我们需要32位来表示一个整数,其中每个数字的可能性相等。减少这个数字的唯一方法,是增加一些数字的概率,减少其他数字的概率。您应该更详细地解释流。

对第二个问题的答复

正确的方法是在与HTTP通信时使用base64。显然Java在标准库中没有这个功能,但我找到了一个指向免费实现的链接:

http://iharder.sourceforge.net/current/java/base64/

下面是“伪代码”,它在Python中工作得非常好,并且应该不难转换为Java(我的Java已经生锈了):

def longTo64(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
    output = ""

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % 64] + output
        num /= 64

    return output

如果您可以控制web服务器和web客户端,并且可以毫无问题地解析整个HTTP请求,则可以升级到base85。根据维基百科, url encoding allows for up to 85 characters

def longTo85(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = ""
    base = len(mapping)

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % base] + output
        num /= base

    return output

这里是逆运算:

def stringToLong(string):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = 0
    base = len(mapping)

    place = 0
    # check each digit from the lowest place
    for digit in reversed(string):
        # find the number the mapping of symbol to number, then multiply by base^place
        output += mapping.find(digit) * (base ** place)
        place += 1

    return output

如您所见,基数越高,表示数字所需的符号就越少。在base64中,需要大约11个符号来表示一个长的。在base85处,它变为约10个符号。

我认为base64是最好的解决方案,因为有处理它的标准函数,而这种想法的变体并没有带来太多改进。这里的其他人对此作出了更详细的回答。

原始答复:

你是说像这样的?

shortest_output = {}

foreach (int R = 0; R <= X; R++) {
    // iteration over possible remainders
    // check if the rest of X can be decomposed into multipliers
    newX = X - R;
    output = {};

    while (newX > Y) {
       int i;
       for (i = Y; i > 1; i--) {
           if ( newX  % i == 0) { // found a divider
           output.append(i);
           newX  = newX /i;  
           break;
           }
       }

       if (i == 1) { // no dividers <= Y
          break;
       }
    }
    if (newX != 1) {
        // couldn't find dividers with no remainder
        output.clear();
    }
    else {
        output.append(R);
            if (output.length() < shortest_output.length()) {
                 shortest_output = output;
            }
    }
}

听起来好像你想压缩随机数据——由于信息论的原因,这是不可能的。(见 http://www.faqs.org/faqs/compression-faq/part1/preamble.html 问题9.)在数字的串联二进制表示形式上使用Base64,然后使用它。

y )被称为 Integer Factorization 如果给定任何已知的算法,则无法有效地执行此操作:

这个问题使许多加密功能成为可能(即使用128位密钥的RSA,长度是它的一半。)wiki页面包含一些很好的资源,可以帮助您解决问题。

所以,你的脑筋急转弯确实是脑筋急转弯。。。如果你能有效地解决这个问题,我们可以将你的数学技能提升到平均水平以上!

更新后的完整故事

进一步打包URL的一种方法是您提到的Base64。

int[] IDs;
IDs.sort() // So IDs[i] is always smaller or equal to IDs[i-1].

string url = Base64Encode(IDs[0]);

for (int i = 1; i < IDs.length; i++) {
  url += "," + Base64Encode(IDs[i-1] - IDs[i]);
}

更新

只是重申问题无法解决。对于Y=64,不能在乘法器+余数中写入87681,其中每一个都低于64。换句话说,您不能用低于64的乘法器写出任何数字87617..87681。每个数字都有一个超过64的基本项。87616可以写在64以下的基本术语中,但是你需要那些+65,所以剩下的将超过64。

因此,如果这只是一个脑筋急转弯,它是无法解决的。除了使用乘法和余数之外,是否还有其他可以实现的实际用途?

是的,这确实应该是一个评论,但我在某个时候失去了评论的能力P

我相信最接近的解决方案是叶夫根尼的。扩展Yevgeny的解决方案以消除余数的限制也很容易,在这种情况下,它将能够找到乘法器小于Y且余数尽可能小的解决方案,即使大于Y。

如果限制数组中的每个数字必须低于y,则没有解决方案。给定足够大的x和足够小的y,你将在一个不可能的情况下结束。例如y为2,x为12,得到2*2*2+4,因为2*2*2*2等于16。即使你允许abs(n)在y以下的负数也不行,因为在上面的例子中你需要2*2*2*2-4。

我认为这个问题是NP完全的,即使你把问题限制在已知答案的输入上,最后一项小于y。这听起来很像[背包问题][1]。当然,我可能错了。

编辑:

如果没有更准确的问题描述,就很难解决问题,但一种变体可能以以下方式工作:

1. 设置电流=x
2. 按规定中断电流
3. 如果其中一个术语大于y,则当前数字不能用大于y的术语描述。从当前减少一个,从2重复。
4. 当前数字可以用小于y的术语表示。
5. 计算余数
6. 结合尽可能多的术语。

OP写道:

我最初的目标是提出 整数(也称为long)组合在一起,以便 比实际写的要短 表示的长度在

我以前也曾走过这条路,为了节省你的时间,我会告诉你,学习所有的数学很有趣: http://en.wikipedia.org/wiki/Kolmogorov_complexity

简而言之,通过更改符号,可以轻松压缩某些字符串:

10^9 (4 characters) = 1000000000 (10 characters)

其他人不能:

7829203478 = some random number...

编辑: 如果您试图为一组唯一的数据创建RESTful URL,为什么不使用散列,比如MD5?然后将散列作为URL的一部分,然后根据散列查找数据。还是我遗漏了一些明显的东西?

您选择的原始方法 (a * b + c * d + e) "+ e" 这会使事情复杂化,因为你不需要进行因式分解 只是

两种压缩弹簧的方法立即浮现在脑海中,这两种方法都可以从数字表示中节省10%以上的空间。

64位数字的范围为(无符号):

                         0 to
18,446,744,073,709,551,616

-9,223,372,036,854,775,808 to
 9,223,372,036,854,775,807

在这两种情况下,您都需要将所使用的20个字符(不带逗号)减少到更小的值。

第一种方法是简单地将base64编码的数字BCD化(实际上是一个稍微修改过的base64) "/" 在URL中不符合犹太教义-您应该使用可接受的字符之一,例如 "_"

将其转换为BCD将把两个数字(或一个符号和一个数字)存储到一个字节中,立即将空间减少50%(10字节)。将其编码为base 64(即每3个字节转换为4个base64字符),将前9个字节转换为12个字符,第10个字节转换为2个字符,总共14个字符,这节省了30%。

唯一更好的方法是只对二进制表示进行base64编码。这更好,因为BCD有少量损耗(每个数字只需要大约3.32位来存储[log] 10] ,但BCD使用4)。

如果你愿意 压缩,有73个字符可用于URL编码:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789$-_.+!*'(),

当然,这是最大值导致的最大压缩。在量表的另一端(1位),这种编码实际上会导致 更多

Range (bytes)  Chars  Base64 chars  Compression ratio
-------------  -----  ------------  -----------------
     < 10 (1)      1       2             -100%
    < 100 (1)      2       2                0%
   < 1000 (2)      3       3                0%
   < 10^4 (2)      4       3               25%
   < 10^5 (3)      5       4               20%
   < 10^6 (3)      6       4               33%
   < 10^7 (3)      7       4               42%
   < 10^8 (4)      8       6               25%
   < 10^9 (4)      9       6               33%
  < 10^10 (5)     10       7               30%
  < 10^11 (5)     11       7               36%
  < 10^12 (5)     12       7               41%
  < 10^13 (6)     13       8               38%
  < 10^14 (6)     14       8               42%
  < 10^15 (7)     15      10               33%
  < 10^16 (7)     16      10               37%
  < 10^17 (8)     17      11               35%
  < 10^18 (8)     18      11               38%
  < 10^19 (8)     19      11               42%
  <  2^64 (8)     20      11               45%

更新:

我现在用另一种方式处理大素数的情况。这样,无论哪种方法都可以得到结果。

public final class PrimeNumberException extends Exception {

    private final long primeNumber;

    public PrimeNumberException(long x) {
        primeNumber = x;
    }

    public long getPrimeNumber() {
        return primeNumber;
    }
}

public static Long[] decompose(long x, long y) {
    try {
        final ArrayList<Long> operands = new ArrayList<Long>(1000);
        final long rest = x % y;
        // Extract the rest so the reminder is divisible by y
        final long newX = x - rest;
        // Go into recursion, actually it's a tail recursion
        recDivide(newX, y, operands);            
    } catch (PrimeNumberException e) {
        // return new Long[0];
        // or do whatever you like, for example
        operands.add(e.getPrimeNumber());
    } finally {
        // Add the reminder to the array
        operands.add(rest);
        return operands.toArray(new Long[operands.size()]);
    }
}

// The recursive method
private static void recDivide(long x, long y, ArrayList<Long> operands)
    throws PrimeNumberException {
    while ((x > y) && (y != 1)) {
        if (x % y == 0) {
            final long rest = x / y;
            // Since y is a divisor add it to the list of operands
            operands.add(y);
            if (rest <= y) {
                // the rest is smaller than y, we're finished
                operands.add(rest);
            }
            // go in recursion
            x = rest;
        } else {
            // if the value x isn't divisible by y decrement y so you'll find a 
            // divisor eventually
            if (--y == 1) {
                throw new PrimeNumberException(x);
            }
        }
    }
}

这里是我提出的一些递归代码。我更愿意用一些函数式语言编写它,但Java是必需的。我没有费心将数字转换成整数,但这应该没那么难(是的,我很懒;)

public static Long[] decompose(long x, long y) {
    final ArrayList<Long> operands = new ArrayList<Long>();
    final long rest = x % y;
    // Extract the rest so the reminder is divisible by y
    final long newX = x - rest;
    // Go into recursion, actually it's a tail recursion
    recDivide(newX, y, operands);
    // Add the reminder to the array
    operands.add(rest);
    return operands.toArray(new Long[operands.size()]);
}

// The recursive method
private static void recDivide(long newX, long y, ArrayList<Long> operands) {
    long x = newX;
    if (x % y == 0) {
        final long rest = x / y;
        // Since y is a divisor add it to the list of operands
        operands.add(y);
        if (rest <= y) {
            // the rest is smaller than y, we're finished
            operands.add(rest);
        } else {
            // the rest can still be divided, go one level deeper in recursion
            recDivide(rest, y, operands);
        }
    } else {
        // if the value x isn't divisible by y decrement y so you'll find a divisor    
        // eventually
        recDivide(x, y-1, operands);
    }
}

本机Python解决方案

我推荐的标准模块是 base64 pickle 模块,它处理从长列表(实际上是任意大小)到压缩字符串表示的转换。

以下代码应适用于任何普通的Python安装:

import base64
import pickle

# get some long list of numbers
a = (854183415,1270335149,228790978,1610119503,1785730631,2084495271,
    1180819741,1200564070,1594464081,1312769708,491733762,243961400,
    655643948,1950847733,492757139,1373886707,336679529,591953597,
    2007045617,1653638786)

# this gets you the url-safe string
str64 = base64.urlsafe_b64encode(pickle.dumps(a,-1))
print str64
>>> gAIoSvfN6TJKrca3S0rCEqMNSk95-F9KRxZwakqn3z58Sh3hYUZKZiePR0pRlwlfSqxGP05KAkNPHUo4jooOSixVFCdK9ZJHdEqT4F4dSvPY41FKaVIRFEq9fkgjSvEVoXdKgoaQYnRxAC4=

# this unwinds it
a64 = pickle.loads(base64.urlsafe_b64decode(str64))
print a64
>>> (854183415, 1270335149, 228790978, 1610119503, 1785730631, 2084495271, 1180819741, 1200564070, 1594464081, 1312769708, 491733762, 243961400, 655643948, 1950847733, 492757139, 1373886707, 336679529, 591953597, 2007045617, 1653638786)

Wrt原始算法请求:最后一个数字的大小是否有限制(超过此限制后,它必须存储在32b整数中)?

bool negative=(n<1)?true:false;
int j=n%y;
if(n==0 || n==1)
{
list.append(n);
return;
}
while((long64)(n-j*y)>MAX_INT && y>1) //R has to be stored in int32
{
y--;
j=n%y;
}
if(y<=1)
fail //Number has no suitable candidate factors. This shouldn't happen

int i=0;
for(;i<j;i++)
{
list.append(y);
}
list.append(n-y*j);
if(negative)
list[0]*=-1;
return;

与目前给出的大多数答案相比有点简单,但它实现了原始帖子的预期功能。。。有点脏,但希望有用:)

这不是模数吗?

允许 / 是整数除(整数)和 % 是模的。

int result[3];

result[0] = y;
result[1] = x / y;
result[2] = x % y;

只需设置x:=x/n,其中n是 最大的

就像我在上面的评论一样,我不确定我是否完全理解这个问题。但是假设整数(n和给定的y),这应该适用于您所述的情况:

multipliers[0] = n / y;
multipliers[1] = y;
addedNumber = n % y;