代码之家 › 专栏 › 技术社区 › Puppy

集合变换

transformation abstract set

2

Puppy · 技术社区 · 15 年前

我正在寻找一种方法来改变一个设置,并有麻烦。这是因为要求相当严格。

集合A包含一堆整数,细节真的不相关。

A中的每个值直接映射到B中的一个且只有一个值。
B中任意N个值的和与a中它的原始值的和有严格的关系。这种关系可能不依赖于知道所讨论的实际N个值,尽管知道总和的值的数目等其他事情是可以的。

例如,只需说B[i]=2^A[i]就可以满足前两个需求。但这并不有用,因为如果你做了2^x=2^A[i]+2^A[j],你就不能推断A[i]和A[j]的和是x或者其他不涉及A[i]或A[j]的表达式。

我倾向于这种转变是不可能的,但我想我会把它扔出去以防万一。

编辑:我一直不清楚。对不起的。这个想法主要存在于我的脑海中。

我已经知道B值的和了。问题是,我从B值的和开始,然后在B中找到和它求和的值,这由于唯一的位限制是微不足道的。问题是,和最初是用A值表示的,所以我必须能够将和从A值的和转换为B值的和。如果我必须对每个可能的和分别进行转换,这对我来说是无用的,因为转换取决于我求和的值。

更多编辑:同样,我从B[i]到A[i]的反向机制是一个查找表。不需要实际存在的数学函数。任何A[i]都是独一无二的。

3 回复 | 直到 15 年前

1

0

Borealid 15 年前

我认为你的第三个约束是个问题。当你说A是B的一对一时,这意味着存在一个可逆映射 F: A->B 与之相反 F': B->A F'(F(x))=x . 现在,“B中任意N个值的和与a中原始值的和有严格的关系”。这意味着存在一些 G 如此 G(A_1+A_2+...+A_n)=B_1+B_2+...+B_n A_1=F'(B_1) ,所以“知道问题中的实际N值”( A_1 through A_n ,尽管您最初的问题让它变得模棱两可,但由于一对一的对应关系,您引用的值)与“知道”B值是相同的。因此,对于有限的整数集,不可能同时满足约束1和约束3;如果指示您“将这些nB值求和”,则已经知道A值了-只需应用反变换。

2

0

Seth 15 年前

3

0

NullUserException Mark Roddy 15 年前

问题是总数是最初用A值表示,所以从a值之和到B值之和价值观。

这就意味着从A值的和中找到A值,如果A值是任意的,我认为这是不可能的。

按照你的描述,这个问题似乎是 subset sum problem ,这是NP完全的。您可以使用动态编程来提高它的性能,但我不知道您是否可以超越这一点。