Stack Overflow
Stack Overflow

Questions tagged [bijection]

In mathematics, a function is a bijection, or is bijective, if it is both injective and surjective.

47 questions
35
votes
11 answers

Symmetric Bijective Algorithm for Integers

I need an algorithm that can do a one-to-one mapping (ie. no collision) of a 32-bit signed integer onto another 32-bit signed integer. My real concern is enough entropy so that the output of the function appears to be random. Basically I am looking…
Emre Yazici
  • 10,136
  • 6
  • 48
  • 55
21
votes
1 answer

Lifting a bijection into a functor

Maybe I'm missing something obvious, but I'm trying to clean up some boilerplate in a project that uses Scalaz 7, and I'm not finding one particular puzzle piece that seems pretty simple and possibly useful. Suppose we have a bijection between two…
Travis Brown
  • 138,631
  • 12
  • 375
  • 680
15
votes
2 answers

Is there an established way to write parsers that can reconstruct their exact input?

Say I want to parse a file in language X. Really, I'm only interested in a small part of the information within. It's easy enough to write a parser in one of Haskell's many eDSLs for that purpose (e.g. Megaparsec). data Foo = Foo Int -- the…
leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
10
votes
2 answers

efficient functional data structure for finite bijections

I'm looking for a functional data structure that represents finite bijections between two types, that is space-efficient and time-efficient. For instance, I'd be happy if, considering a bijection f of size n: extending f with a new pair of elements…
esope
  • 760
  • 3
  • 12
7
votes
5 answers

Bijective "Integer <-> String" function

Here's a problem I'm trying to create the best solution for. I have a finite set of non-negative integers in the range of [0...N]. I need to be able to represent each number in this set as a string and be able to convert such string backwards to…
andrew.z
  • 1,039
  • 3
  • 15
  • 24
7
votes
2 answers

Is there "good" PRNG generating values without hidden state?

I need some good pseudo random number generator that can be computed like a pure function from its previous output without any state hiding. Under "good" I mean: I must be able to parametrize generator in such way that running it for 2^n iterations…
actual
  • 2,370
  • 1
  • 21
  • 32
7
votes
2 answers

Pseudo-random-looking one-to-one int32->int32 function

I am looking for a int32->int32 function that is bijection (one-to-one correspondence) cheap to calculate at least in one direction transforms the increasing sequence 0, 1, 2, 3, ... into a sequence looking like a good pseudo-random sequence (~…
Vladimir Reshetnikov
  • 11,750
  • 4
  • 30
  • 51
6
votes
5 answers

Find possible bijection between characters and digits

Let's say you have a string S and a sequence of digits in a list L such that len(S) = len(L). What would be the cleanest way of checking if you can find a bijection between the characters of the string to the digits in the sequence such that each…
Ehsan Kia
  • 1,475
  • 18
  • 26
4
votes
1 answer

Create a random bijective function which has same domain and range

Create a random bijective function which has same domain and range. By random bijective function I mean a function which maps the elements from domain to range using a random algorithm (or at least a pseudo-random algo), and not something like x=y.…
tom
  • 172
  • 1
  • 10
4
votes
2 answers

Minimize the cost of transformation

I came up with the following problem but I am not able to find a solution for it. Statement: There are N wine glasses. Each wine glass is assumed to have infinite capacity. The amount of wine in each glass is a positive non-zero integer, where the…
Guru Prasad
  • 127
  • 1
  • 6
3
votes
4 answers

Sort or remove elements from corresponding list in same way as in reference list

I have two lists in python of same length: listA = [7,6,3,2,1,4,5] listB = [a,b,c,d,e,f,g] is their some way (probably easy function) to sort listA and change the values of listB in the same way. Means listA_new = [1,2,3,4,5,6,7] and listB_new =…
Martin Kunze
  • 995
  • 6
  • 16
3
votes
1 answer

Bijection between (n choose k) and bitstrings of length n with k bits set

While I know how to generate all (n choose k) bitstrings of size n with exactly k bits set to one, I'm struggling finding a bijection, that gets as input a number i between 1 and (n choose k) and outputs the i-th vector of that kind in an arbitrary…
Memphisd
  • 307
  • 1
  • 8
3
votes
1 answer

Define bijection in Agda

The question is how do we define bijection in agda? definition: We know that 2 + 2 = 2 × 2 = 2^2 = 4 for numbers. Similarly, we have that Bool + Bool ∼= Bool × Bool ∼= Bool → Bool where A ∼= B means that there is a bijection between A and B, that…
MarabouBarYog
  • 31
  • 1
3
votes
1 answer

JBoss Seam: inject in @Create method possible?

I cannot seem to be able to inject a Seam component inside the @Create method. I cannot find in the documentation any hint that this is not possible, which would verify whether I am making a mistake or not. Is it possible to inject inside the…
Markos Fragkakis
  • 7,499
  • 18
  • 65
  • 103
3
votes
0 answers

Why there are no bijective datatypes

I recently ran into a situation where I needed to add reverse lookup functionalities in my mappings, and then I was surprised by the fact there there are simply no datatypes designed for this kind of bijection. I was able to get around using two…
Matthew Yang
  • 605
  • 1
  • 13
  • 23
1
2 3 4