Stack Overflow
Stack Overflow

Questions tagged [equivalence-classes]

Use equivalence-classes for questions related to decomposing a set into subsets in which each element produces a constant output given a constant input

References

42 questions
95
votes
4 answers

Union of 2 sets does not contain all items

How come when I change the order of the two sets in the unions below, I get different results? set1 = {1, 2, 3} set2 = {True, False} print(set1 | set2) # {False, 1, 2, 3} print(set2 | set1) #{False, True, 2, 3}
Blueplastic
  • 803
  • 7
  • 11
54
votes
19 answers

Python: simple list merging based on intersections

Consider there are some lists of integers as: #-------------------------------------- 0 [0,1,3] 1 [1,0,3,4,5,10,...] 2 [2,8] 3 [3,1,0,...] ... n [] #-------------------------------------- The question is to merge lists having at least one common…
Developer
  • 8,258
  • 8
  • 49
  • 58
19
votes
4 answers

Many-to-one mapping (creating equivalence classes)

I have a project of converting one database to another. One of the original database columns defines the row's category. This column should be mapped to a new category in the new database. For example, let's assume the original categories…
Adam Matan
  • 128,757
  • 147
  • 397
  • 562
11
votes
1 answer

Equivalence classes and union/find in a functional language

For an automata algorithm, I require a fast Union-Find data structure in a functional language. Since I need to formally prove the correctness of the data structure, I would prefer a simple structure. What I am trying to do is to compute the…
Manuel Eberl
  • 7,858
  • 15
  • 24
10
votes
6 answers

Is there a standard way to partition an interable into equivalence classes given a relation in python?

Say I have a finite iterable X and an equivalence relation ~ on X. We can define a function my_relation(x1, x2) that returns True if x1~x2 and returns False otherwise. I want to write a function that partitions X into equivalence classes. That is,…
Brian Fitzpatrick
  • 2,443
  • 2
  • 14
  • 14
8
votes
1 answer

Java: external class for determining equivalence?

Java has a Comparator for providing comparison of objects external to the class itself, to allow for multiple/alternate methods of doing ordered comparisons. But the only standard way of doing unordered comparisons is to override equals() within…
Jason S
  • 184,598
  • 164
  • 608
  • 970
7
votes
3 answers

What's a good data structure for building equivalence classes on nodes of a tree?

I'm looking for a good data structure to build equivalence classes on nodes of a tree. In an ideal structure, the following operations should be fast (O(1)/O(n) as appropriate) and easy (no paragraphs of mystery code): (A) Walk the tree from the…
MarkusQ
  • 21,814
  • 3
  • 56
  • 68
7
votes
2 answers

Implementing equivalence relations in C++ (using boost::disjoint_sets)

Assume you have many elements, and you need to keep track of the equivalence relations between them. If element A is equivalent to element B, it is equivalent to all the other elements B is equivalent to. I am looking for an efficient data…
D R
  • 21,936
  • 38
  • 112
  • 149
6
votes
3 answers

Microsoft.VisualBasic.FileIO.FileSystem equivalence in C#

I use VS 2008, .net 3.5, C# projects. I need do the same functionally like Microsoft.VisualBasic.FileIO.FileSystem.DeleteDirectory. Anyone says referencing the Microsoft.VisualBasic is often undesirable from within C#. Any association with VB from…
Kiquenet
  • 14,494
  • 35
  • 148
  • 243
5
votes
3 answers

Definition of Equality

When overloading the "==" operator in c++, is there a standard definition as to what equality explicitly means, or a set of guidelines as how "==" should behave? I currently have a class that does not store its entire self in memory. It basically…
David Saxon
  • 1,406
  • 1
  • 12
  • 23
4
votes
1 answer

What is the meaning of "equivalence class" in the context of regular expressions?

In certain flavours of regular expression, inside a square bracket expression, the = symbol is a special character that is used as a delimiter for enclosing any one the elements within an equivalence class. The documentation says the following: An…
user16095614
4
votes
3 answers

awk and equivalence classes

Does gnu awk support POSIX equivalence classes? Is it possible to match [[=a=]] using awk as it is done in grep? $ echo ábÅ | grep [[=a=]] ábÅ $ echo ábÅ | grep -o [[=a=]] á Å
Eugene Barsky
  • 5,780
  • 3
  • 17
  • 40
3
votes
3 answers

Form array of equivalence related classes

I have an array in Matlab. I numbered every entry in array with natural number. So I formed equivalence relation in array. For example, array = [1 2 3 5 6 7] classes = [1 2 1 1 3 3]. I want to get cell array: i-th cell array's position is…
Macaronnos
  • 647
  • 5
  • 14
2
votes
1 answer

What are the Equivalent Classes?

Let A = {a, b, c, d, e, f, g, h, i} and R be a relation on A as follows: R={(a,a), (f,c), (b,b), (c,f), (a,d), (c,c), (c,i), (d,a), (b,e), (i,c), (e,b), (d,d), (e,e), (f,f), (g,g), (h,h), (i,i), (h,e), (a,g), (g,a), (d,g), (g,d), (b,h), (h,b),…
alex
  • 21
  • 4
2
votes
1 answer

Combine tuples in a list which have the same value

I have a list with tuples like this: L ={(1,2), (1,4), (1,3), (2,3), (3,4), (3,5), (4,5), (6,7)} I try to combine these to get equivalence classes (tuples of the same value are merged, like (1,2) and (2,3) becomes (1,2,3)). So you get: EQ =…
Bas
  • 881
  • 1
  • 10
  • 23
1
2 3