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’s statement. (source Brute-force search – Wikipedia)
Sample applications
- Computing an
- Computing n!
- Multiplication two matrices
- Searching for a given value in the list
- BOYER MOORE ALGORITHM
- Selection Sort
1. Computing an
// A naive C++ solution to count solutions of
// a + b + c = n
//Given a number n, find a number of ways we can add 3 non-negative integers so that their sum is n.
/*
Input : n = 1
Output : 3
There are four ways to get sum 1.
(1, 0, 0), (0, 1, 0) and (0, 0, 1)
Input : n = 2
Output : 6
There are six ways to get sum 2.
(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0)
(1, 0, 1) and (0, 1, 1)
Input : n = 3
Output : 10
There are ten ways to get sum 10.
(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0)
(1, 0, 2), (0, 1, 2), (2, 1, 0), (2, 0, 1),
(0, 2, 1) and (1, 1, 1)
*/
#include<iostream>
using namespace std;
// Returns count of solutions of a + b + c = n
int countIntegralSolutions(int n)
{
// Initialize result
int result = 0;
// Consider all triplets and increment
// result whenever sum of a triplet is n.
for (int i=0; i<=n; i++)
for (int j=0; j<=n-i; j++)
for (int k=0; k<=(n-i-j); k++)
if (i + j + k == n){
cout << "("<< i << ", " << j <<", "<< k << ")"<<endl;
result++;
}
return result;
}
int main()
{
int n;
cout << "Enter n: ";
cin >> n;
cout << countIntegralSolutions(n);
return 0;
}
2. Computing n!
#include <iostream>
using namespace std;
int main()
{
int n;
unsigned long long factorial = 1;
cout << "Enter a positive integer: ";
cin >> n;
if (n < 0)
cout << "Error! Factorial of a negative number doesn't exist.";
else {
for(int i = 1; i <=n; ++i) {
factorial *= i;
cout << i << " * " << i+1 << " = " <<factorial << endl;
}
cout << "Factorial of " << n << " = " << factorial;
}
return 0;
}
3. Multiplication two matrices
#include <iostream>
using namespace std;
int main()
{
int a[10][10],b[10][10],mul[10][10],r,c,i,j,k;
cout<<"enter the number of row=";
cin>>r;
cout<<"enter the number of column=";
cin>>c;
cout<<"enter the first matrix element=\n";
for(i=0;i<r;i++){
for(j=0;j<c;j++){
cin>>a[i][j];
}
}
cout<<"enter the second matrix element=\n";
for(i=0;i<r;i++) {
for(j=0;j<c;j++){
cin>>b[i][j];
}
}
cout<<"multiply of the matrix=\n";
for(i=0;i<r;i++) {
for(j=0;j<c;j++) {
mul[i][j]=0;
for(k=0;k<c;k++) {
mul[i][j]+=a[i][k]*b[k][j];
}
}
}
//for printing result
for(i=0;i<r;i++) {
for(j=0;j<c;j++){
cout<<mul[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
4. Searching for a given value in the list
//brute force algorithm
//string matching
import java.io.*;
import java.util.Scanner;
class Bruteforce{
//called function
public static int bruteforce(String text,String tobematched){
int length = text.length();//length of the text
int plength = tobematched.length();//length of the pattern;
//loop condition
for(int i=0;i<length-plength;i++){
//initialization of j
int j=0;
while((j < plength) && (text.charAt(i+j) == tobematched.charAt(j))){
j++;
}
if(j == plength){
return i;
}
}
return -1;
}
public static void main(String[] args){
Bruteforce obj = new Bruteforce();
Scanner sc = new Scanner(System.in);
//text
String text = "I Love Programming and I do Programming";
//word that want to be matched in the text
String tobematched = "Programming";
//calling the function
int position = obj.bruteforce(text,tobematched);
int endindex = position+1;
//condition to check whether the pattern is matched are not
if(position == -1){
System.out.println("Pattern is not matched in the text");
}else{
System.out.println("Found at position:" + (position+1));
System.out.println("End at the position:" + (endindex + tobematched.length()));
}
}
}
BRUTE FORCE STRING
public class BruteForceSearch {
//return the index
public static int search(String text, String pattern){
int lengthOfText = text.length();
int lengthOfPattern = pattern.length();
//loop
//This is just a test!
// just
//lengthOfText - lengthOfPattern -- no match sa last text kasi test! vs just which is 4 char
for( int i = 0; i < lengthOfText - lengthOfPattern ; i++){
//System.out.println("K"+(lengthOfText - lengthOfPattern));
int j; // for the pattern
//iterage in the pattern
for( j=0;j<lengthOfPattern;j++){
//mismatch
if( text.charAt(i+j) != pattern.charAt(j)){
break;
}
}
//found
if( j == lengthOfPattern ) return i;
//return i+1
}
//mismatch return length of text
return lengthOfText;
}
public static void main(String[] args) {
String text = "This is just a test!";
String pattern = "just";
int lengthOfText = text.length();
int lengthOfPattern = pattern.length();
System.out.println("lengthOfText"+lengthOfText);
System.out.println("lengthOfPattern"+lengthOfPattern);
System.out.println(search(text, pattern));
}
}
BOYER MOORE ALGORITHM
public class Bru2 {
public static void main(String[] args) {
String text = "This is a test";
String pattern = "test";
BoyerMoore boyerMoore = new BoyerMoore(text, pattern);
boyerMoore.precomputeShifts();
System.out.println( boyerMoore.search() );
}
}
//-------------------------------------
import java.util.HashMap;
import java.util.Map;
public class BoyerMoore {
private Map<Character, Integer> mismatchShiftsTable;
private String text;
private String pattern;
public BoyerMoore(String text, String pattern) {
this.pattern = pattern;
this.text = text;
this.mismatchShiftsTable = new HashMap<>();
}
public void precomputeShifts() {
int lengthOfPattern = this.pattern.length();
for (int index = 0; index < lengthOfPattern; index++) {
char actualCharacter = this.pattern.charAt(index);
int maxShift = Math.max(1, lengthOfPattern - index - 1);
this.mismatchShiftsTable.put(actualCharacter, maxShift);
}
}
public int search() {
int lengthOfPattern = this.pattern.length();
int lengthOfText = this.text.length();
int numOfSkips;
for (int i = 0; i <= lengthOfText - lengthOfPattern; i += numOfSkips) {
numOfSkips = 0;
for (int j = lengthOfPattern - 1; j >= 0; j--) {
if (pattern.charAt(j) != text.charAt(i + j)) {
if ( this.mismatchShiftsTable.get(text.charAt(i+j)) != null ) {
numOfSkips = this.mismatchShiftsTable.get(text.charAt(i+j));
System.out.println(numOfSkips);
break;
} else {
numOfSkips = lengthOfPattern;
System.out.println(numOfSkips);
break;
}
}
}
if (numOfSkips == 0) return i;
}
return lengthOfText;
}
}
import java.util.HashMap;
import java.util.Map;
public class BoyerMoore {
private Map<Character, Integer> mismatchShiftsTable;
private String text;
private String pattern;
public BoyerMoore(String text, String pattern) {
this.pattern = pattern;
this.text = text;
this.mismatchShiftsTable = new HashMap<>();
}
public void precomputeShifts() {
int lengthOfPattern = this.pattern.length();
for (int index = 0; index < lengthOfPattern; index++) {
char actualCharacter = this.pattern.charAt(index);
int maxShift = Math.max(1, lengthOfPattern - index - 1);
this.mismatchShiftsTable.put(actualCharacter, maxShift);
}
}
public int search() {
int lengthOfPattern = this.pattern.length();
int lengthOfText = this.text.length();
int numOfSkips;
for (int i = 0; i <= lengthOfText - lengthOfPattern; i += numOfSkips) {
numOfSkips = 0;
for (int j = lengthOfPattern - 1; j >= 0; j--) {
if (pattern.charAt(j) != text.charAt(i + j)) {
if ( this.mismatchShiftsTable.get(text.charAt(i+j)) != null ) {
numOfSkips = this.mismatchShiftsTable.get(text.charAt(i+j));
System.out.println(numOfSkips);
break;
} else {
numOfSkips = lengthOfPattern;
System.out.println(numOfSkips);
break;
}
}
}
if (numOfSkips == 0) return i;
}
return lengthOfText;
}
}