标签: bijection

我需要一种能够将32位有符号整数与另一个32位有符号整数进行一对一映射(即无冲突)的算法.

我真正关心的是足够的熵,因此函数的输出似乎是随机的.基本上我正在寻找类似于XOR Cipher的密码,但它可以生成更多任意外观的输出.虽然默默无闻,但安全并不是我真正关心的问题.

编辑以便澄清:

1. 算法必须是对称的,这样我就可以在没有密钥对的情况下反转操作.
2. 该算法必须是双射的,每个32位输入数必须生成一个32位唯一编号.
3. 函数的输出必须足够模糊,只在输入中添加一个应该对输出产生很大影响.

预期结果示例:

F(100)= 98456
F(101)= -758F
(102)= 10875498
F(103)= 986541
F(104)= 945451245
F(105)= -488554

就像MD5一样,改变一件事可能会改变很多事情.

我正在寻找一个数学函数,所以手动映射整数不是我的解决方案.对于那些提出要求的人来说,算法速度并不是很重要.

也许我错过了一些明显的东西,但我正在尝试清理一个使用Scalaz 7的项目中的一些样板,而我找不到一个看似非常简单且可能有用的特殊拼图.

假设我们有两种类型的双射:

case class Foo(x: Int)
case class Bar(i: Int)

import scalaz._, Scalaz._, BijectionT._

val fb: Foo <@> Bar = bijection[Id, Id, Foo, Bar](
  foo => Bar(foo.x),
  bar => Foo(bar.i)
)

现在假设我们发现我们需要List[Foo]和之间的双射List[Bar].我们可以轻松编写一个提供此功能的隐式类(实际上我们也可以使它适用于任何仿函数):

implicit class BijectionLifter[A, B](val bij: A <@> B) extends AnyVal {
  def liftInto[F[_]: Functor]: F[A] <@> F[B] = bijection[Id, Id, F[A], F[B]](
    _ map bij.to,
    _ map bij.from
  )
}

请注意,这是bimapHaskell的直接翻译Data.Bijection.Scalaz的双射也有一个名为的方法bimap,但它有一个更繁忙的类型,似乎没有以任何明显的方式做我想要的.

现在我们可以写下面的内容:

fb.liftInto[List]

我们得到了我们需要的双射.

我是否遗漏了一些抽象,这使得我可以用Scalaz 7中已经提供的用于双射的函数和实例更清晰地编写它？

假设我想用语言X解析文件.真的,我只对其中的一小部分信息感兴趣.为此目的在Haskell的许多eDSL中编写解析器很容易(例如Megaparsec).

data Foo = Foo Int  -- the information I'm after.

parseFoo :: Parsec Text Foo
parseFoo = ...

这很容易产生一种功能getFoo :: Text -> Maybe Foo.

但现在我还要修改信息的来源Foo,即基本上我想实现

changeFoo :: (Foo -> Foo) -> Text -> Text

与属性

changeFoo id ? id
getFoo . changeFoo f ? fmap f . getFoo

可以通过将解析器的结果更改为类似镜头的方式来实现

parseFoo :: Parsec Text (Foo, Foo -> Text)
parseFoo = ...

但是这使定义变得更加麻烦 - 我不能仅仅string掩盖不相关的信息,而是需要存储每个subparse 的匹配并手动重新组装它.

这可以通过将字符串重组保持在StateT解析器monad周围的层中来实现自动化,但我不能只使用现有的原始解析器.

这个问题是否有现成的解决方案？

我正在寻找一种功能数据结构,它代表两种类型之间的有限双射,即节省空间和节省时间.

例如,考虑到大小为n的双射f,我会很高兴:

• 用一对新元素扩展f具有复杂度O(ln n)
• 查询f(x)或f ^ -1(x)具有复杂度O(ln n)
• f的内部表示比具有2个有限映射(表示f及其逆)更节省空间

我知道排列的有效表示,就像本文一样,但似乎并没有解决我的问题.

我需要一些好的伪随机数生成器,它可以像以前的输出中的纯函数一样计算,而不会隐藏任何状态.在"好"下我的意思是:

1. 我必须能够参数化以这样的方式产生器,其运行它用于2^n与任何参数(或与他们的一些大的子集)的迭代应涵盖之间所有或几乎所有的值0和2^n - 1,其中n是在输出值的比特数.

2. 组合的发生器n + p比特输出必须覆盖所有或几乎所有的值0,2^(n + p) - 1如果我2^n为其参数的每个可能组合进行迭代运行,其中p是参数中的位数.

例如,LCG可以像纯函数一样计算,它可以满足第一个条件,但它不能满足第二个条件.比方说,我们有32位LCG,m = 2^32它是常量,我们p = 64(两个32位参数a和c)n + p = 96,所以我们必须从输出中查看数据三个整数以满足第二个条件.不幸的是,由于输出中奇数和偶数整数的严格交替顺序,条件不能满足.为了克服这个问题,必须引入隐藏状态,但这会使函数变得不纯净并破坏第一个条件(长隐藏期).

编辑:严格来说,我希望函数族通过p位和完整的n位状态进行参数化,每个函数都p + n以独特的"随机"方式生成所有可能的二进制位串,而不仅仅是连续递增(p + n)-bit int.选择独特方式所需的参数化.

我想要太多了吗？

我正在寻找一个int32-> int32函数

• 双向(一对一对应)
• 便宜至少在一个方向上计算
• 将增加的序列0,1,2,3 ......转换成一个看起来像一个好的伪随机序列的序列(当参数变化较小时,〜半位翻转,没有明显的模式)

假设你有一个字符串S和一个列表L中的数字序列,len(S)= len(L).

检查是否可以在字符串的字符与序列中的数字之间找到双射,以使每个字符与一个且仅一个数字匹配,这是最干净的方法.

例如,"aabbcc"应与115522匹配,但不匹配123456或111111.

我有一个复杂的设置,有两个dicts和循环,但我想知道是否有一个干净的方法,可能通过使用Python库中的一些函数.

这是一个问题,我正在尝试为其创建最佳解决方案.我有一组有限的非负整数,范围为[0 ... N].我需要能够将此集合中的每个数字表示为字符串,并能够将此字符串向后转换为原始数字.所以这应该是一个双射函数.

其他要求是:

1. 数字的字符串表示应该至少在某种程度上模糊原始数字.像f(x)= x.toString()这样的原始解决方案是行不通的.
2. 字符串长度很重要:越少越好.
3. 如果知道K的字符串表示,我希望猜测K + 1的字符串表示是非平凡的(在某种程度上).

对于p.1和p.2,显而易见的解决方案是使用类似Base64(或任何BaseXXX以适合所有值)的表示法.但是我们能否以最小的额外努力适应p.3？常识告诉我,我还需要一个双射"String < - > String"函数用于BaseXXX值.有什么建议？或者可能有比BaseXXX更好的东西来满足所有3个要求？

我似乎无法在@Create方法中注入Seam组件.我在文档中找不到任何暗示这是不可能的,这将验证我是否犯了错误.

是否有可能注入@Create？

干杯!

什么是测试a是否Map[A,B]是双射的简单方法,即for

val m1 = Map( 1 -> "a", 2 -> "b")
val m2 = Map( 1 -> "a", 2 -> "a")

我们认为这m1是双射的m2.

我有两个阵列,说A={1, 2, 3}和B={2, 4, 8}(数组项计数和编号可能不同).如何在阵列之间找到双射.

在这种情况下,它会 f:A->B; f(x)=2^(x)