0

让我举个例子，让我们考虑一下字符串：1000 0101 0111 0000

以及全范围的 2 位字符串：00 01 10 11

我想知道是否有一个函数具有逆并将 4 个 4 位字符串映射到 2 位字符串。

4

2 回答 2

0

从一组 n 个元素到另一组 n 个元素的双射数是 n!

连续考虑每个目标元素，并选择其匹配的源元素。首先，您可以在 n 中进行选择。对于第二个，您可以在 (n-1) 之间进行选择。...

您想要 4 个元素的集合之间的双射，因此您有 4 个！= 24 种可能的功能。

00 将在其中六个（3！）中映射到 1000，在其中六个中映射到 0101，依此类推。

我不确定这是否能回答您的问题，但这就是我的理解。

于 2011-03-19T05:55:03.223 回答
0

对于 4 4 位的情况，您有 16 ** 4 或 65536 个情况，这将映射到 8 个 2 位单元，因此这将是一个微不足道的问题。但是，如果您将问题重述为由 4 位到每个字节 2 位组成的所有字符串的空间的双射映射，这是一个不同的问题，是的，有一个解决方案。

一个简单的解决方案是查看每种模式到无限奇数二进制字符串空间的映射。无限奇数字符串的最后一个距离开始有限的距离你所做的是你开始写入位，因为它们出现你有一个标志，如果它设置并且你已经完成了最后一个字节（无论是 2 位还是 4 位，无论你使用）你写一个 1000... 如果标志是明确的，你写 000... 因为有一个是扩展中的最后一个“1”。

  • 对于 2 位集
  • 00 设置标志
  • 10 不做任何标记

  • 剩下的 01 11 清除标志

  • 对于 4 位集

  • 0000 设置标志
  • 1000 对标记没有任何作用
  • 其余都包含至少 1 个或多个并清除标志

将 1000 0101 0111 0000 转换为 100001010111000010000 的直接副本...注意尾部 100 .. 因为设置了标志。如果您对 2 位设置执行相反的操作，则标志会经历许多状态，但 1000.. 在标志的末尾部分，因此在 2 位设置中您会得到 10 00 01 01 01 11 00 00 没什么大不了的 8 个字节

但是在转换 1000 0101 0111 0100 时，您会得到 1000010101110000 ... 当查看 2 位设置时，您会得到 10 00 01 01 01 11 10，这是一个 2 位单元短 7 个字节

对于从 4 位集到 2 位集的这种双射，对于两个字节的字节或 2n-1 个字节，其中 n 个 4 位字节的字节数总是有 2n 个字节。

这种映射到无限奇数文件的方法适用于任何字符串的双射变换，该字符串是每个字节的任意字节数的无限集合的成员，即使构成一个字节的位数随 n 的函数而变化。

于 2012-01-19T00:07:02.767 回答