设置变换
我正在寻找一种改造集合的方法，但遇到了麻烦。这是因为要求相当严格。
集合A包含一堆整数，细节确实无关紧要。
集合 B 包含一堆整数，这样：
- A 中的每个值直接映射到 B 中的一个且仅有一个值。
- B 中的一个且仅有一个值的每一位为真。 B 中的
- 任何 N 个值的总和有与 A 中原始值（的总和）的严格关系。这种关系可能不依赖于了解所讨论的实际 N 值，尽管了解总和值的数量等其他事情也很好。
这主要是一个思想练习，而不是实际的实现，因此详细说明了内存约束的实际情况，例如，内存约束会随着 A 的大小而大幅增长。
例如，您可以通过简单地说 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] 与任何其他 A[j] 都是唯一的。
I'm looking for a way to transform a set, and having trouble. This is because the requirements are rather rigorous.
Set A contains a bunch of integers, the details are really irrelevant.
Set B contains a bunch of integers, such that:
- Each value in A directly maps to one and only one value in B.
- Each bit is true in one, and only one, value in B.
- The sum of any N values in B has a strict relation to (the sum of) it's original values in A. This relation may not depend on knowing the actual N values in question, although other things like knowing the number of values summed is fine.
It's mainly a thought exercise rather than an actual implementation, so detailing the realities of, for example, the memory constraints which would grow hugely with the size of A.
For example, you could satisfy the first two requirements by simply saying that B[i] = 2^A[i]. But that's not useful, because if you did 2^x = 2^A[i] + 2^A[j], you can't infer that the sum of A[i] and A[j] is x or some other expression which does not involve A[i] or A[j].
I'm tending towards such a transformation being impossible, but thought I'd throw it out there just in case.
Edit: I've been unclear. Sorry. This idea exists mainly in my head.
I already know the sum of the B values. The problem is that I start with the sum of the B values and find the values in B which sum to it, which is trivial due to the unique-bits restriction. The trouble is that the sum is initially expressed in A values, so I have to be able to transform the sum from a sum of A values to a sum of B values. This is useless to me if I have to transform it separately for every possible sum because the transformation depends on the values I'm summing.
More edit: Also, my reverse mechanism from B[i] to A[i] is a lookup table. Don't need an actual existent mathematical function. Any A[i] is unique from any other A[j].
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为你的第三个限制提出了问题。当你说 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； B 值之和与 A 值相关。但是，由于第一个子句，我们已经确定A_1=F'(B_1)，因此“了解相关的实际 N 值”（A_1 到 A_n，尽管您最初的问题使您所指的值含糊不清）与“了解” B 值相同，因为它们是一一对应的。因此，对于有限整数集，不可能同时满足约束一和约束三；如果您被指示“对这 n 个 B 值求和”，您必须已经知道 A 值 - 只需应用逆变换即可。I think your third constraint poses a problem. When you say A is one-to-one onto B, that means there exists an invertible mapping
F: A->Band its inverseF': B->Asuch thatF'(F(x))=x. Now, "the sum of any N values in B has a strict relation to the sum of the original values in A". This means that there exists someGsuch thatG(A_1+A_2+...+A_n)=B_1+B_2+...+B_n; the sum of the B-values are related to the A-values. But, because of the first clause, we've established thatA_1=F'(B_1), so "knowing the actual N values in question" (A_1 through A_n, although your original question leaves it ambiguous to which values you refer) is the same as "knowing" the B-values, due to the one-to-one correspondence. Thus it is not possible to satisfy constraints one and three simultaneously for a finite set of integers; if you are instructed to "sum these n B-values", you must already know the A-values - just apply the inverse transform.给定 (A_1 + ... + A_n)，我们可以假设每个 A_i 都是唯一的吗？如果不是，则该问题是不可能的：将 A_1 与其自身相加 A_2 次，与将 A_2 与其自身相加 A_1 次得到相同的结果。如果每个 A_i 都是唯一的，那么我们可以对 A 和 B 之间的双射做出什么假设？例如，如果 N 已知，则 A[i] = B[i] + d 对于所有 d 来说都是可逆的。即使我们可以假设总和中的每个 A_i 都是唯一的，当（且仅当）A 的两个子集之和不等于相同值时，恢复 B_i 的问题也是可能的。 B_i 恢复的容易程度取决于双射的性质。
Given (A_1 + ... + A_n), can we assume each A_i is unique? If not, the problem is impossible: adding A_1 to itself A_2 times gives the same result as adding A_2 to itself A_1 times. If each A_i IS unique, then what are we allowed to assume about the bijection between A and B? For example, if N is known, then A[i] = B[i] + d is trivially reversible for all d. Even if we can assume each A_i in the sum is unique, the problem of recovering the B_i is possible if (and only if) no two subsets of A sum to the same value. How easily the B_i can be recovered depends on the nature of the bijection.
这意味着从 A 值的总和中找到 A 值，如果 A 值是任意的，我认为这是不可能的。
编辑：按照您描述的方式，这个问题似乎是 子集和问题，这是 NP 完全的。您可以使用动态编程来提高其性能，但我不知道您是否可以超越此范围。
That translates to finding the A values from a sum of A values, which I don't think is possible if the A values are arbitrary.
EDIT: The way you described it, this problem appears to be the subset sum problem, which is NP-complete. You can use dynamic programming to improve its performance, but I don't know if you can go much beyond that.