Can This Property (Representative Property) Be Generalized? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:12:33Z https://cs.stackexchange.com/feeds/question/24160 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/24160 1 Can This Property (Representative Property) Be Generalized? aliatlii https://cs.stackexchange.com/users/17125 2014-04-27T23:19:38Z 2014-06-02T04:49:51Z <p>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:</p> <p>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.</p> <p>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.</p> <p>İ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.</p> <p>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.</p> <p>This is the code for who wonders all work...</p> <pre><code>import java.util.Scanner; import java.util.ArrayList; public class Quest_1 { private static boolean isRelativePrime(ArrayList&lt;Integer&gt; newInfo) { int j; for(int i=newInfo.size()-1;i&gt;=0;i--){ for(int k=i-1;k&gt;=0;k--){ j=2; while (j&lt;newInfo.get(k)||j&lt;newInfo.get(i)){ if(newInfo.get(k)%j == 0 &amp;&amp; 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 &gt;= 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&gt;0){ if (i%2==0) empty = empty +"0"; else empty = empty +"1"; i = i/2; count++; } while(count &lt; 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&lt;Integer&gt; info = new ArrayList&lt;Integer&gt;(); ArrayList&lt;Integer&gt; newInfo = new ArrayList&lt;Integer&gt;(); for (int i = 0;i&lt;componentSize;i++){ info.add(scan.nextInt()); } for(int l=0;l&lt;info.size();l++) System.out.println("***----****------****** "+info.get(l)); for(int k=(int)Math.pow(2, componentSize)-1; k&gt;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 &gt;= 0){ if(binary.charAt(index)=='1') newInfo.add(info.get(index)); index--; } if(isRelativePrime(newInfo) &amp;&amp; max&lt;newInfo.size()) max = newInfo.size(); index=newInfo.size()-1; while(index&gt;=0){ newInfo.remove(index); index--; } } System.out.println("here is the max: "+max); } } </code></pre> <p>Now here comes the question. Can this way, I mean representing the computations with numbers , be generalized?</p> <p>For example: there is a password whose length is 5. "1" stands for a, "2" for b and etc.</p> <p>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?</p> <p>I am majoring CS, first semester. Therefore, I am open to all suggestions.</p> <p>(I am really sorry for everything wrong, I'd really appreciated,if you kindly warned me.)</p> https://cs.stackexchange.com/questions/24160/-/24165#24165 1 Answer by Yuval Filmus for Can This Property (Representative Property) Be Generalized? Yuval Filmus https://cs.stackexchange.com/users/683 2014-04-28T01:09:02Z 2014-04-28T01:09:02Z <p>What you're suggesting is a very simple example of <em>combinatorial enumeration</em>. 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.</p> <p>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:</p> <ol> <li>Put $n$ at one of the $n$ available spots.</li> <li>Put $n-1$ at one of the $n-1$ available spots.</li> <li>Go on until you put $1$ the only available spot.</li> </ol> <p>Here $B_i = i$, and we get a way to enumerate permutations.</p> <p>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.</p>