1
$\begingroup$

I recently came across with a question that asks for the greatest subset of a given set, which includes relatively prime elements.(Randomly selected item from a set is always relatively prime to all others.) My approach was eliminating the subsets depending on if the subset satisfies the rule. Which means testing one by one all possible subsets. In order to determine which subset is going to be tested, I have choosen the following way:

Let S be a set and "n" is the size of the set. Since there are 2^n possible subsets, all computer needs to do is to check all possible subsets. However, the question is in which way and regarding what property. In other words what would be the "rule" for computer to do it.

I came up with a method which I call "Representative Property". By using ones and zeroes I could represent all the elements of the set to indicate their existance or absence in the subset which is going to be tested.

İf n=5, then There is 32 possible subsets. Starting from 2^n -1 in which case 31, converting 31 to binary we get "11111". What binary 11111 represent is all the elements of the set is included in the subset which is going to be tested.

By incrementing that value by one I could get 11110,11101,11100,...00010,00001 where "1" stands for existance of the element and the "0" is vice versa.

This is the code for who wonders all work...

import java.util.Scanner;
import java.util.ArrayList;

public class Quest_1 {

private static boolean isRelativePrime(ArrayList<Integer> newInfo) {
    int j;
    for(int i=newInfo.size()-1;i>=0;i--){

        for(int k=i-1;k>=0;k--){
            j=2;
            while (j<newInfo.get(k)||j<newInfo.get(i)){
                if(newInfo.get(k)%j == 0 && newInfo.get(i)%j== 0)
                    return false;
                j++;
            }
        }
    }
    return true;
}
public static String reverse(String source) {
    int i, len = source.length();
    StringBuffer dest = new StringBuffer(len);

    for (i = (len - 1); i >= 0; i--)
        dest.append(source.charAt(i));
    return dest.toString();
}
public static String binary(int i, int k){


    int count = 0;
    String empty ="";

    while(i>0){

        if (i%2==0)
            empty = empty +"0";
        else
            empty = empty +"1";
        i = i/2;
        count++;

    }

    while(count < k){
        empty = empty+"0";
        count++;
    }
    empty = reverse(empty);
    return empty;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.print("Kaç eleman? ");
    String binary;
    int max = 0;
    int componentSize = scan.nextInt();

    ArrayList<Integer> info = new ArrayList<Integer>();
    ArrayList<Integer> newInfo = new ArrayList<Integer>();
    for (int i = 0;i<componentSize;i++){

        info.add(scan.nextInt());

    }
    for(int l=0;l<info.size();l++)
        System.out.println("***----****------****** "+info.get(l));
    for(int k=(int)Math.pow(2, componentSize)-1; k>0; k--){
        // takes the string.if "1" add,then compare.if relatPrime is true omit, else leave it
        binary = binary( k, componentSize);
        int index=binary.length()-1;
        while(index >= 0){

            if(binary.charAt(index)=='1')
                newInfo.add(info.get(index));

            index--;
        }
        if(isRelativePrime(newInfo) && max<newInfo.size())
            max = newInfo.size();
        index=newInfo.size()-1;
        while(index>=0){
            newInfo.remove(index);
            index--;
        }
    }
    System.out.println("here is the max: "+max);
}

}

Now here comes the question. Can this way, I mean representing the computations with numbers , be generalized?

For example: there is a password whose length is 5. "1" stands for a, "2" for b and etc.

or for chess games, by decrementing the test case number, Can all the possibilities be evaluated ? And what is this process called,checking all the possibilities?

I am majoring CS, first semester. Therefore, I am open to all suggestions.

(I am really sorry for everything wrong, I'd really appreciated,if you kindly warned me.)

$\endgroup$
  • 2
    $\begingroup$ Your representation of a set by a sequence of bits is known as the "characteristic vector" of the set. Yes, it can be generalized. For example, you can view a string of letters a-z as a number in base 26 in just the same way as you view a string of digits 0-9 as a number in base 10. Beyond that, I'm not really sure what you're asking. $\endgroup$ – David Richerby Apr 28 '14 at 0:36
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Jun 2 '14 at 7:32
1
$\begingroup$

What you're suggesting is a very simple example of combinatorial enumeration. In your case, you're enumerating the power set $$\{0,1\}^S.$$ List the items of $S$ in some arbitrary order: $S = \{s_1,\ldots,s_n\}$. We can write $$ \{0,1\}^S = \{0,1\}^{s_1,\ldots,s_{n-1}} \cup \{0,1\}^{s_1,\ldots,s_{n-1}} \times \{s_n\}. $$ This means that a subset of $S$ is either a subset of $\{s_1,\ldots,s_{n-1}\}$ or such a subset together with $s_n$. There are $2^{n-1}$ of each, so the corresponding equation on cardinalities reads $$ 2^n = 2^{n-1} + 2^{n-1}. $$ The idea is to think of this in terms of intervals: $$ [0,2^n) = [0,2^{n-1}) + [2^{n-1},2^n). $$ (Here $[a,b) = \{a , a+1 , \ldots , b-1 \}$.) We can encode an arbitrary subset of $S$ by recursively encoding a subset of $\{s_1,\ldots,s_{n-1}\}$ as some integer $x \in [0,2^{n-1})$, and then putting it in the first interval $[0,2^{n-1})$ if $s_n$ is not in the subset, or in the second interval $2^{n-1} + [0,2^{n-1}) = [2^{n-1},2^n)$ if $s_n$ is in the subset. What we get is the binary encoding of the subset which you describe.

More generally, if each element can receive one out of $B$ colors, we get base $B$ encoding (in your case $B = 2$ since each element is either "in" or "out"). The number of colors can even vary depending on the element: if there are $B_i$ possible colors for $s_i$, then we get a mixed base notation. A good example is $S_n$, the set of permutations of $\{1,\ldots,n\}$, which can be described in the following way:

  1. Put $n$ at one of the $n$ available spots.
  2. Put $n-1$ at one of the $n-1$ available spots.
  3. Go on until you put $1$ the only available spot.

Here $B_i = i$, and we get a way to enumerate permutations.

This method works even more generally. For example, using the recurrence for Catalan numbers, we can encode binary trees. Using Pascal's identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$, we can encode $\binom{[n]}{k}$ (subsets of $\{1,\ldots,n\}$ of size $k$). And so on.

$\endgroup$
  • $\begingroup$ This is a way to enumerate all subsets of $S$, but (if I understood the question) the author was asking for a way to find the largest subset of $S$ such that all elements in the subset are pairwise relatively prime. There might be a better way to solve that problem than by enumerating all subsets of $S$. $\endgroup$ – D.W. Apr 28 '14 at 3:27
  • $\begingroup$ @D.W. I think that the particular question you're mentioning is the background to the actual question, which is about encoding subsets and numbers and possible generalizations. $\endgroup$ – Yuval Filmus Apr 28 '14 at 3:51
  • 1
    $\begingroup$ The original question is NP-complete, by reduction from independent set. Choose a prime for each edge, and let each vertex be the product of the primes adjacent to it. $\endgroup$ – Yuval Filmus Apr 28 '14 at 3:54
  • $\begingroup$ Since I am a first grade student, in fact, I could not concieve much of the answer.However, when googled some keywords, as far as I understand, this is the answer. Thank you!! $\endgroup$ – aliatlii Apr 28 '14 at 19:44
  • $\begingroup$ @YuvalFilmus what about permutations. By using combinatorial enumeration, can we list permutations of a set as well ? $\endgroup$ – aliatlii May 30 '14 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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