Brute Force Algorithm

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

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;
	}
}