Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I set up equivalence relationships for subsets of a set of integers, such that subsets are only equivalent if they possess the same elements (and use banking ordering described below)?

I am trying to order subsets of a set of numbers (nominally a set of cards).

Assume for now that each suit has an order (CLUBS, DIAMONDS, HEARTS, SPADES) and each Rank has an order (2...10,J,Q,K,A) so that $C4>C3$, and that $C4<D2$. This can be simplified by ordering $C2-SA \equiv 1..52$ etc and thus the set in question contains all elements from one to fifty two, e.g. $\{1..52\}$.

I need to be able to place (by operating on both sets some how) each of the subsets at a unique point in an order such that no two sets are equal unless they contain the exact same elements. Perhaps an example would be helpful here:

$$\begin{matrix}\{4,1\} = \{1,4\}&\text{(1)}\\ \{2,3\} = \{3,2\}&\text{(2)}\\ \{2,3\} \ne \{4,1\}&\text{(3)}\end{matrix}$$

Naturally to me, I would assume that as the subsets $(3)$ sum to the same that they could be considered equivalent, but for my purposes it turns out that summing elements (which would be the operation) is not a sufficient way of operating on both sets some how As this means that two distinct subsets occupy the same place in the ordering. It'd be like having $4=5$.

After looking up a paper on ordering sets, I discovered the banking order which seems like a better way to order subsets.

tabular image of the banking order

Note the notion here is similar as to Lexigraphical ordering ( also in the paper in which the digits represent each individual element directly, so the 3rd digit is a 1 or a 0 if the 3rd element is or isn;t present in the subset), but we can no longer use the binary digits as a way of ordering the subsets.

Is there an operation (e.g. $f(setA,setB)$) that would give an equivalence relation between two subsets using Banking ordering? Preferably one that gives this relationship:

$$\begin{cases}1&\text{SetA > SetB}\\-1&\text{SetA < SetB}\\0&\text{SetA}\equiv\text{SetB}\end{cases}$$

Is this possible?

share|improve this question
    
First, your "score" only takes one input and then you define it to take two inputs? Doesn't really make sense. –  Raskolnikov Jun 22 '13 at 10:30
    
@Raskolnikov apologies, I was messing/mixing up scores for each set, and the result of comparing the two scores for the pair of sets. I hope that makes more sense. –  Pureferret Jun 22 '13 at 11:36
    
You could compare the entire set A against set B: What is the first card that is in just one of the two sets? That set is greater than the other set. This works because you are treating each set as a 52-digit binary number. –  Michael Jun 22 '13 at 11:48
    
Why is SetA greater than SetB just because they're not equal? And I don't get why you have to multiply the result of the signum function by the maximum score between the sets. Don't you just want to return which set is greater, with no more information? –  markovchain Jun 22 '13 at 12:02
    
@markovchain I've just generalised that specific example. I hope it's clearer now. –  Pureferret Jun 22 '13 at 13:07

3 Answers 3

This method gives each set a pair of scores, then a quick comparison:
1. Represent the set by a 52-vector (a1,a2,...,a52)
where aj = 1 if card j is in the set, 0 if card j is not.
2. Calculate A1=a1+2*a2+4*a3+8*a4+...+33554432*a26
3. Calculate A2=a27+2*a28+4*a29+...+33554432*a52
4. Compare set A with set B by comparing A1 against B1.
If they match, compare A2 against B2

I would combine steps 2 and 3 into a single number, but integers don't always go up that high.

In the new ordering, you might need three numbers:
1. A1 = number of cards in the set.
2. A2 = 33554432*a1+...+4*a24+2*a25+a26
3. A3 = 33554432*a27+...+2*a51+a52

share|improve this answer
    
Why assign the powers of 2 to each card, especially that any card could go into any slot? It seems more intuitive to assign values to each card and just sum those up. –  markovchain Jun 22 '13 at 13:03
    
There are $2^{52}$ different possible sets, and he wants each set to have a different score –  Michael Jun 22 '13 at 13:29
    
Ah. Well in that case, you make sense. Your program asks for 0's or 1's (where the program must display the cards you're checking), whereas I understood it as the program asking you what card it is. Two questions though: why not account for the fact that all cards come in 4 suits of equal value (the maximum is only 2^13), and why does 33554432 not have a square root? –  markovchain Jun 22 '13 at 13:40
    
I realize that my first question should be directed to the OP, @Pureferret –  markovchain Jun 22 '13 at 13:47
    
@Michael After looking into order theory, I see your method has merit! However, I'm not sure if it works with all ordering methods. Could you please check out my recent edit and let me know? –  Pureferret Jun 24 '13 at 14:54

For the new ordering, and assuming there are $52$ items (the changes for an arbitrary number should be clear) you need to order the items in importance. Now we are looking for a bijection between the numbers $[0,2^{52}-1]$ and the subsets that respects the order you have requested. So suppose we want to find the subset that corresponds to a certain number, say 123456789. The first thing is to find how many elements are in the subset. There are ${52 \choose 0}=1$ subsets with no elements, ${52 \choose 1}=52$ with one, ${52 \choose 2}=1326$ and so on. So keep adding these until you get greater than the index. We find there are $ 23251684$ with six or less elements, so we want the $123456789-23251684=100205105$th one of the seven element subsets. The first card is in the first ${51 \choose 6}=18009460$ of them, so we want the $82195645$th one not including the first card. The second card is in the next ${50 \choose 6}= 15890700$ of them, so it is not in the one we want and we look for the $66304945$th one of what is left. This lends itself to dynamic programming and can be done rather efficiently.

share|improve this answer

Correct me if I'm wrong, but I understand it as a very simple problem (hence I'm doubting if I understood your intention correctly), and I would solve your problem this way.

  1. Initialize your array1[52] and array2[52], and all other variables you need
  2. Initialize their values to zero using for(int i=0; i<52; i++){array1[i]=0; array2[i]=0;}
  3. Ask for the values/scores of your cards. Your metric might be 5 for 5S, 5D, 5H, 5C, etc

OR 2. Already initialize the values into the arrays, if you don't want to input the numbers

  1. Sum all numbers in the array with for(int i=0; i<52; i++){Sa+=array1[i]; Sb+=array2[i];}
  2. Compare. If(Sa < Sb){ Print("Deck B wins");} elseif(Sa > Sb){ Print("Deck A wins");} else {Print("It's a draw");}

Was that right? Or did I misunderstand you?

share|improve this answer
1  
Since your decks don't always have to be 52, you could also add a prompt after every input if the user wants to continue, OR (as I would prefer) you could set it so that entering, say, the letter "X" would stop the program from asking you for that particular deck. –  markovchain Jun 22 '13 at 13:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.