Hello

the question concerns not the API and mechanisms of the language, but the algorithms

in short, her wording is as follows: we have two sets, between which there is a mapping. It may be injective and / or surjective. It is necessary to determine whether it is possible to select from the given set of links the subset corresponding to the bijection.

if closer to the subject matter, the first set is the actual values, the second is the expected ones. The order for both sets does not matter. For the expected registered operation, applying it to the current we get the boolean value. For example, actual = "abc" operation = "endsWith" expected = "c" returns true: actual is a prototype of expected. And here we have two such sets of the same size, and we need to establish whether they are displayed biologically in each other. The only working option that I still have is brutessing. But I would not want to. Is it possible to establish by any criteria the possibility of separating a bijective display without going through all the possible options? (For example, the criterion "each element of both sets must have at least one connection" is necessary, but not sufficient, and checking whether each preimage from the actual map to its image in expected is already brute force). Maybe there are some theorems, based on which, you can build an algorithm? I would love to read something on this topic.

thank

  • one
    What is the size of the set? So the matching problem ... Algorithms are simple, the complexity is about linear in random graphs. - pavel
  • Mostly small, no more than 10 values ​​are expected, but in principle are possible for 1000+ - Artem Bykov
  • one
    For a mapping to be bijectively necessary and sufficient for it to be injective (that is, different elements of the source set are mapped to different elements of the target set) and surjective (that is, all elements of the target set can be obtained from the source set) - Anton Shchyrov
  • one
    If, as you say, both sets of the same size, then surjectivity will automatically mean injectivity, otherwise nothing :) - Yaant
  • one
    Well, we are now talking about the case when the cardinalities of the sets (let A and B) coincide. If each element B is a pattern of at least one single element A, then the power of the pre-image B (let's call it C) must be not less than the power of B: | C | > = | B |, on the one hand, C is a subset of A, that is, | C | <= | A |, on the other hand, | A | = | B |. It follows that | C | = | A |, and since we are talking about finite sets, then C = A .. - Yaant

0