{"id":398,"date":"2021-05-31T14:46:41","date_gmt":"2021-05-31T14:46:41","guid":{"rendered":"https:\/\/xcodeph.net\/?page_id=398"},"modified":"2021-06-09T00:53:33","modified_gmt":"2021-06-09T00:53:33","slug":"brute-force-algorithm","status":"publish","type":"page","link":"https:\/\/xcodeph.net\/index.php\/brute-force-algorithm\/","title":{"rendered":"Brute Force Algorithm"},"content":{"rendered":"\n<p>In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem&#8217;s statement. (source <a href=\"https:\/\/en.wikipedia.org\/wiki\/Brute-force_search\">Brute-force search &#8211; Wikipedia<\/a>)<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h2><strong>Sample applications<\/strong><\/h2>\n\n\n\n<ul><li><a href=\"#a\">Computing a<sup>n<\/sup><\/a><\/li><li><a href=\"#b\">Computing n!<\/a><\/li><li><a href=\"#c\">Multiplication two matrices<\/a><\/li><li><a href=\"#d\">Searching for a given value in the list<\/a><\/li><li><a href=\"#e>BRUTE FORCE STRING<\/a><\/li><li><a href=\" #f\"=\"\">BOYER MOORE ALGORITHM<\/a><\/li><li><a href=\"#g\">Selection Sort<\/a><\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<h2><strong><a name=\"a\">1. Computing <\/a>a<sup>n<\/sup><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">\/\/ A naive C++ solution to count solutions of\n\/\/ a + b + c = n\n\/\/Given a number n, find a number of ways we can add 3 non-negative integers so that their sum is n.\n\/*\nInput : n = 1\nOutput : 3\nThere are four ways to get sum 1.\n(1, 0, 0), (0, 1, 0) and (0, 0, 1)\n\nInput : n = 2\nOutput : 6\nThere are six ways to get sum 2.\n(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0)\n(1, 0, 1) and (0, 1, 1)\n\nInput : n = 3\nOutput : 10\nThere are ten ways to get sum 10.\n(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0)\n(1, 0, 2), (0, 1, 2), (2, 1, 0), (2, 0, 1),\n(0, 2, 1) and (1, 1, 1)\n*\/\n\n#include&lt;iostream>\nusing namespace std;\n \n\/\/ Returns count of solutions of a + b + c = n\nint countIntegralSolutions(int n)\n{\n    \/\/ Initialize result\n    int result = 0;\n \n    \/\/ Consider all triplets and increment\n    \/\/ result whenever sum of a triplet is n.\n    for (int i=0; i&lt;=n; i++)\n      for (int j=0; j&lt;=n-i; j++)\n          for (int k=0; k&lt;=(n-i-j); k++)\n            if (i + j + k == n){\n              cout &lt;&lt; \"(\"&lt;&lt; i &lt;&lt; \", \" &lt;&lt; j &lt;&lt;\", \"&lt;&lt; k &lt;&lt; \")\"&lt;&lt;endl;\n              result++;\n            }\n    return result;\n}\n \nint main()\n{\n    int n;\n    cout &lt;&lt; \"Enter n: \";\n    cin >> n;\n    cout &lt;&lt;  countIntegralSolutions(n);\n    return 0;\n}<\/pre>\n\n\n\n<h2><strong><a name=\"b\">2. Computing n!<\/a><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">#include &lt;iostream>\nusing namespace std;\n\nint main()\n{\n    int n;\n    unsigned long long factorial = 1;\n\n    cout &lt;&lt; \"Enter a positive integer: \";\n    cin >> n;\n\n    if (n &lt; 0)\n        cout &lt;&lt; \"Error! Factorial of a negative number doesn't exist.\";\n    else {\n        for(int i = 1; i &lt;=n; ++i) {\n            factorial *= i;\n            cout &lt;&lt; i &lt;&lt; \" * \" &lt;&lt; i+1 &lt;&lt; \" = \" &lt;&lt;factorial &lt;&lt; endl;\n        }\n        cout &lt;&lt; \"Factorial of \" &lt;&lt; n &lt;&lt; \" = \" &lt;&lt; factorial;    \n    }\n\n    return 0;\n}<\/pre>\n\n\n\n<h2><strong><a name=\"c\">3. Multiplication two matrices<\/a><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">#include &lt;iostream>  \nusing namespace std;  \nint main()  \n{  \n\tint a[10][10],b[10][10],mul[10][10],r,c,i,j,k;    \n\tcout&lt;&lt;\"enter the number of row=\";    \n\tcin>>r;    \n\tcout&lt;&lt;\"enter the number of column=\";    \n\tcin>>c;    \n\tcout&lt;&lt;\"enter the first matrix element=\\n\";    \n\tfor(i=0;i&lt;r;i++){    \n\t\tfor(j=0;j&lt;c;j++){    \n\t\t\tcin>>a[i][j]; \n\t\t}\n\t}\n\tcout&lt;&lt;\"enter the second matrix element=\\n\";    \n\tfor(i=0;i&lt;r;i++) {    \n\t\tfor(j=0;j&lt;c;j++){    \n\t\t\tcin>>b[i][j];    \n\t\t}    \n\t}    \n\tcout&lt;&lt;\"multiply of the matrix=\\n\";    \n\tfor(i=0;i&lt;r;i++) {    \n\t\tfor(j=0;j&lt;c;j++) {    \n\t\t\tmul[i][j]=0;    \n\t\t\tfor(k=0;k&lt;c;k++) {    \n\t\t\t\tmul[i][j]+=a[i][k]*b[k][j];    \n\t\t\t}    \n\t\t}    \n\t}    \n\t\/\/for printing result    \n\tfor(i=0;i&lt;r;i++) {    \n\t\tfor(j=0;j&lt;c;j++){    \n\t\t\tcout&lt;&lt;mul[i][j]&lt;&lt;\" \"; \n\t\t}    \n\t\tcout&lt;&lt;\"\\n\";    \n\t}    \n\treturn 0;  \n}<\/pre>\n\n\n\n<h2><strong><a name=\"d\">4. Searching for a given value in the list<\/a><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">\/\/brute force algorithm\n\/\/string matching\nimport java.io.*;\nimport java.util.Scanner;\n\nclass Bruteforce{\n\t\/\/called function\n\tpublic static int bruteforce(String text,String tobematched){\n\t\tint length = text.length();\/\/length of the text\n\t\tint plength = tobematched.length();\/\/length of the pattern;\n\n\t\t\/\/loop condition\n\t\tfor(int i=0;i&lt;length-plength;i++){\n\t\t\t\/\/initialization of j\n\t\t\tint j=0;\n\t\t\twhile((j &lt; plength) &amp;&amp; (text.charAt(i+j) == tobematched.charAt(j))){\n\t\t\t\tj++;\n\t\t\t}\n\t\t\tif(j == plength){\n\t\t\t\treturn i;\n\t\t\t}\n\t\t}\n\n\t\treturn -1;\n\t}\n\n\tpublic static void main(String[] args){\n\t\tBruteforce obj = new Bruteforce();\n\t\tScanner sc =  new Scanner(System.in);\n\t\t\/\/text\n\t\tString text = \"I Love Programming and I do Programming\";\n\t\t\/\/word that want to be matched in the text\n\t\tString tobematched = \"Programming\";\n\t\t\/\/calling the function\n\t\tint position = obj.bruteforce(text,tobematched);\n\t\tint endindex = position+1;\n\t\t\/\/condition to check whether the pattern is matched are not\n\t\tif(position == -1){\n\t\t\tSystem.out.println(\"Pattern is not matched in the text\");\n\t\t}else{\n\t\t\tSystem.out.println(\"Found at position:\" + (position+1));\n\t\t\tSystem.out.println(\"End at the position:\" + (endindex + tobematched.length()));\n\t\t}\n\t}\n}\n\n<\/pre>\n\n\n\n<h2><strong><a name=\"e\">BRUTE FORCE STRING <\/a><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">\npublic class BruteForceSearch {\n\t\/\/return the index\n\tpublic static int search(String text, String pattern){\n\t\t\n\t\tint lengthOfText = text.length();\n\t\tint lengthOfPattern = pattern.length();\n\t\t\n\t\t\/\/loop   \n\t\t\/\/This is just a test!\n\t\t\/\/        just\n\t\t\/\/lengthOfText - lengthOfPattern -- no match sa last text kasi test! vs just which is 4 char \n\t\tfor( int i = 0; i &lt; lengthOfText - lengthOfPattern ; i++){\n\t\t\t\/\/System.out.println(\"K\"+(lengthOfText - lengthOfPattern));\n\t\t\tint j; \/\/ for the pattern\n\t\t\t\n\t\t\t\/\/iterage in the pattern\n\t\t\tfor( j=0;j&lt;lengthOfPattern;j++){\n\t\t\t\t\/\/mismatch\n\t\t\t\tif( text.charAt(i+j) != pattern.charAt(j)){\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t\t\/\/found\n\t\t\tif( j == lengthOfPattern ) return i;\n\t\t\t\/\/return i+1\n\t\t}\n\t\t\/\/mismatch return length of text\n\t\treturn lengthOfText;\n\t}\n\tpublic static void main(String[] args) {\n\t\t\n\t\tString text = \"This is just a test!\";\n\t\tString pattern = \"just\";\n\t\t\n\t\tint lengthOfText = text.length();\n\t\tint lengthOfPattern = pattern.length();\n\t\t\n\t\tSystem.out.println(\"lengthOfText\"+lengthOfText);\n\t\tSystem.out.println(\"lengthOfPattern\"+lengthOfPattern);\n\t\tSystem.out.println(search(text, pattern));\n\t\t\n\t}\n}\n<\/pre>\n\n\n\n<h2><strong><a name=\"f\">BOYER MOORE ALGORITHM<\/a><\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">\npublic class Bru2 {\n\n\tpublic static void main(String[] args) {\n\t\t\n\t\tString text = \"This is a test\";\n\t\tString pattern = \"test\";\n\t\t\n\t\tBoyerMoore boyerMoore = new BoyerMoore(text, pattern);\n\t\tboyerMoore.precomputeShifts();\n\t\tSystem.out.println( boyerMoore.search() );\n\n\t}\n}\n\n\/\/-------------------------------------\nimport java.util.HashMap;\nimport java.util.Map;\n\npublic class BoyerMoore {\n\t\n\tprivate Map&lt;Character, Integer> mismatchShiftsTable;\n\tprivate String text;\n\tprivate String pattern;\n\t\n\tpublic BoyerMoore(String text, String pattern) {\n\t\tthis.pattern = pattern;\n\t\tthis.text = text;\n\t\tthis.mismatchShiftsTable = new HashMap&lt;>();\n\t}\n\t\n\tpublic void precomputeShifts() {\n\t\t\n\t\tint lengthOfPattern = this.pattern.length();\n\t\t\n\t\tfor (int index = 0; index &lt; lengthOfPattern; index++) {\n\t\t\tchar actualCharacter = this.pattern.charAt(index);\n\t\t\tint maxShift = Math.max(1, lengthOfPattern - index - 1);\n\t\t\tthis.mismatchShiftsTable.put(actualCharacter, maxShift);\n\t\t}\n\t}\n\t\n\tpublic int search() {\n\t\t\n\t\tint lengthOfPattern = this.pattern.length();\n\t\tint lengthOfText = this.text.length();\n\t\tint numOfSkips;\n\t\t\n\t\tfor (int i = 0; i &lt;= lengthOfText - lengthOfPattern; i += numOfSkips) {\n\t\t\t\n\t\t\tnumOfSkips = 0;\n\t\t\t\n\t\t\tfor (int j = lengthOfPattern - 1; j >= 0; j--) {\n\t\t\t\tif (pattern.charAt(j) != text.charAt(i + j)) {\n\t\t\t\t\t\n\t\t\t\t\tif ( this.mismatchShiftsTable.get(text.charAt(i+j)) != null ) {\n\t\t\t\t\t\tnumOfSkips = this.mismatchShiftsTable.get(text.charAt(i+j));\n\t\t\t\t\t\tSystem.out.println(numOfSkips);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t} else {\n\t\t\t\t\t\tnumOfSkips = lengthOfPattern;\n\t\t\t\t\t\tSystem.out.println(numOfSkips);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\t\n\t\t\tif (numOfSkips == 0) return i;\n\t\t}\n\t\t\n\t\treturn lengthOfText;\n\t}\n}\n\n<\/pre>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">import java.util.HashMap;\nimport java.util.Map;\n\npublic class BoyerMoore {\n\n\tprivate Map&lt;Character, Integer> mismatchShiftsTable;\n\tprivate String text;\n\tprivate String pattern;\n\n\tpublic BoyerMoore(String text, String pattern) {\n\t\tthis.pattern = pattern;\n\t\tthis.text = text;\n\t\tthis.mismatchShiftsTable = new HashMap&lt;>();\n\t}\n\n\tpublic void precomputeShifts() {\n\n\t\tint lengthOfPattern = this.pattern.length();\n\n\t\tfor (int index = 0; index &lt; lengthOfPattern; index++) {\n\t\t\tchar actualCharacter = this.pattern.charAt(index);\n\t\t\tint maxShift = Math.max(1, lengthOfPattern - index - 1);\n\t\t\tthis.mismatchShiftsTable.put(actualCharacter, maxShift);\n\t\t}\n\t}\n\n\tpublic int search() {\n\n\t\tint lengthOfPattern = this.pattern.length();\n\t\tint lengthOfText = this.text.length();\n\t\tint numOfSkips;\n\n\t\tfor (int i = 0; i &lt;= lengthOfText - lengthOfPattern; i += numOfSkips) {\n\n\t\t\tnumOfSkips = 0;\n\n\t\t\tfor (int j = lengthOfPattern - 1; j >= 0; j--) {\n\t\t\t\tif (pattern.charAt(j) != text.charAt(i + j)) {\n\n\t\t\t\t\tif ( this.mismatchShiftsTable.get(text.charAt(i+j)) != null ) {\n\t\t\t\t\t\tnumOfSkips = this.mismatchShiftsTable.get(text.charAt(i+j));\n\t\t\t\t\t\tSystem.out.println(numOfSkips);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t} else {\n\t\t\t\t\t\tnumOfSkips = lengthOfPattern;\n\t\t\t\t\t\tSystem.out.println(numOfSkips);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tif (numOfSkips == 0) return i;\n\t\t}\n\n\t\treturn lengthOfText;\n\t}\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem&#8217;s statement. (source Brute-force search &#8211; Wikipedia) Sample applications Computing an Computing n! Multiplication [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/398"}],"collection":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/comments?post=398"}],"version-history":[{"count":14,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/398\/revisions"}],"predecessor-version":[{"id":511,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/398\/revisions\/511"}],"wp:attachment":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/media?parent=398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}