任意の(制限された)無限集合とその順序付けられていない対の間に可換の注入関数を設計する

関連していますが、これは正の整数を必要とするだけであり、可換である必要はありません

カンターペアリング機能は、このWikipediaの記事で説明されています。基本的には、XとYの2つの値に適用すると、結果が与えられたときに元の値XとYを得ることができるような演算です。

Your task is to design two functions: one which performs
X, Y -> Z and the other which performs Z
-> X, Y
. Here’s the catch: X, Y -> Z must
be commutative. This means that Z -> X, Y won’t be
able to determine if the input was X, Y or Y,
X
.

この課題の正式な定義は、次のとおりです。

無数の無限集合Sを選択します。
次のタスクを実行する2つの関数を設計します。

  • Sで順序付けされていない値のペアが与えられた場合、Sで値を返します
  • 初期関数からの戻り値が与えられた場合、最初の関数を渡すときに評価される順序のない値のペアを入力整数に返します。入力が最初の関数からの戻り値でない場合、この逆関数の振る舞いは気にしません。

要件

  • The result should be identical between runs.
  • {a, a} is an unordered pair

注:あなたの答えはあなたが証拠を提出すれば私からupvoteを得る可能性が高いですが、私はそれがうまくいくと確信したらそれを取得し、upvoteに答えをテストします。

ベストアンサー

Haskell, 65 + 30 = 95 bytes

a#b=length.fst$span(<(max a b,min a b))[(a,b)|a<-[1..],b<-[1..a]]

Try it
online!

([(a,b)|a<-[1..],b<-[1..a]]!!)

オンラインで試してみてください!


Note: When the two functions may share code,
this is only 75 bytes:

(l!!)
a#b=length.fst$span(<(max a b,min a b))l
l=[(a,b)|a<-[1..],b<-[1..a]]

Try it
online!
The domain is the positive integers. The function
(#) performs the pairing, the function
(l!!) its inverse. Usage example: Both (#) 5
3
and (#) 3 5 yield 12, and
(l!!) 12 yields (5,3).

これは、すべてのソートされたペアを無限リスト l に明示的にリストすることによって動作します。

l = [(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4),(5,5),(6,1), ...`

エンコーディングは、このリストのインデックスにすぎません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です