Posted on by Kalkicode
Code Array

Combine array elements by occurrence sequence

Rearranging array elements based on their occurrence sequence is a common problem in programming. The goal is to arrange the elements of the array in such a way that elements with higher occurrences come before elements with lower occurrences. This rearrangement can help visualize data distribution and simplify certain data processing tasks.

Problem Statement

Given an array of integers, rearrange the elements in a way that elements with higher occurrences are placed before elements with lower occurrences. The order of elements within each occurrence group remains unchanged.

Example

Consider the following array:

arr = [5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3]

After rearranging based on occurrence sequence:

arr = [5, 5, 5, 4, 4, 1, 1, 3, 3, 3, 2, 2]

Idea to Solve

To solve this problem, you can use a combination of recursive and swapping techniques. The general idea is to iterate through the array, and for each element, swap it with the first occurrence of that element in the remaining part of the array. This process is repeated recursively until the entire array is processed.

Pseudocode

function arrange(arr, size, index, counter):
    if index < 0:
        return
    
    data = arr[index]
    arrange(arr, size, index - 1, counter)
    
    for i from counter to size - 1:
        if arr[i] == data:
            swap(arr[i], arr[counter])
            counter += 1

Algorithm Explanation

  1. The recursive function arrange takes the array, its size, the current index, and a counter variable as parameters.
  2. If the index becomes negative, the recursion ends.
  3. For the current element at index index, the function first calls itself recursively with the next index.
  4. Then, it iterates from the counter to the end of the array. If the element matches the current element, it swaps the current element with the element at the counter position and increments the counter.
  5. This process ensures that elements with higher occurrences move to the left side of the array, while elements with lower occurrences remain towards the right.

Code Solution

//C Program 
//Arrange array elements by occurrence sequence
#include <stdio.h>

//Print the array element
void print_data(int arr[],int size)
{   
    
  for(int i=0;i<size;i++)
  {
    printf("%4d",arr[i] );
  }
  printf("\n");
}

void arrange(int arr[],int size,int index,int *counter)
{
  if(index<0) 
  {
    return;
  }
  //Get element
  int data=arr[index];

  arrange(arr,size,index-1,counter);


  for (int i = *counter; i < size && *counter<size ; ++i)
  {
    if(arr[i]==data )
    {
      //swap element value
      arr[i]=arr[*counter];
      arr[*counter]=data;
      (*counter)=*counter+1;
    }

  }
}

int main()
{
   
    int arr[] = { 5, 4,1,3, 5, 5, 3, 1, 2, 2, 4 ,3};
    //Get the size of array
    int size=(sizeof(arr)/sizeof(arr[0]));

    int counter = 1;
    printf("  Before Combine \n");
    print_data(arr,size);
    printf("  After Combine \n");
    arrange(arr,size,size-1,&counter);
    print_data(arr,size);
   
   
    return 0;
}

Output

  Before Combine
   5   4   1   3   5   5   3   1   2   2   4   3
  After Combine
   5   5   5   4   4   1   1   3   3   3   2   2
/*
 C++ Program
 Arrange array elements by occurrence sequence
*/
#include<iostream>

using namespace std;

class MyArray {
	public:
		int counter;
	MyArray() {
		this->counter = 0;
	}
	//Print array elements
	void print_data(int arr[], int size) {
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	void arrange(int arr[], int size, int index) {
		if (index < 0) {
			return;
		}
		//Get element
		int data = arr[index];
		this->arrange(arr, size, index - 1);
		for (int i = this->counter; i < size && this->counter < size; ++i) {
			if (arr[i] == data) {
				//swap element value
				arr[i] = arr[this->counter];
				arr[this->counter] = data;
				this->counter = this->counter + 1;
			}
		}
	}
	void combine_element(int arr[], int size) {
		this->counter = 1;
		this->arrange(arr, size, size - 1);
	}
};
int main() {
	MyArray obj ;
	int arr[] = {
		5,
		4,
		1,
		3,
		5,
		5,
		3,
		1,
		2,
		2,
		4,
		3
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << " Before Combine \n";
	obj.print_data(arr, size);
	cout << " After Combine \n";
	obj.combine_element(arr, size);
	obj.print_data(arr, size);
	return 0;
}

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 5 5 4 4 1 1 3 3 3 2 2
/*
  Java Program
  Arrange array elements by occurrence sequence
*/
public class MyArray {

  public int counter ;

  public MyArray()
  {
    counter = 0;
  }

  //Print array elements
  public void print_data(int []arr,int size)
  {
    
    for(int i = 0; i < size; i++)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }

  public void arrange(int []arr,int size,int index)
  {
    if(index<0) 
    {
      return;
    }
    //Get element
    int data=arr[index];

    arrange(arr,size,index-1);

    for (int i = counter; i < size && counter<size ; ++i)
    {
      if(arr[i]==data )
      {
        //swap element value
        arr[i] = arr[counter];
        arr[counter] = data;
        counter = counter+1;
      }
    }
  }
  void combine_element(int arr[],int size)
  {
    counter = 1;
    arrange(arr,size,size-1);
  }


  public static void main(String[] args) {

    MyArray obj = new MyArray();

    int []arr = { 5, 4,1,3, 5, 5, 3, 1, 2, 2, 4 ,3};
    //Get the size of array
    int size=arr.length;


    System.out.print("  Before Combine \n");
    obj.print_data(arr,size);
    System.out.print("  After Combine \n");
    obj.combine_element(arr,size);
    obj.print_data(arr,size);

  }
}

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 5 5 4 4 1 1 3 3 3 2 2
/*
  C# Program
  Arrange array elements by occurrence sequence
*/
using System;
public class MyArray {

	public int counter;

	public MyArray() {
		counter = 0;
	}

	//Print array elements
	public void print_data(int[] arr, int size) {

		for (int i = 0; i < size; i++) {
			Console.Write("  " + arr[i]);
		}
		Console.Write("\n");
	}

	public void arrange(int[] arr, int size, int index) {
		if (index < 0) {
			return;
		}
		//Get element
		int data = arr[index];

		arrange(arr, size, index - 1);

		for (int i = counter; i < size && counter < size; ++i) {
			if (arr[i] == data) {
				//swap element value
				arr[i] = arr[counter];
				arr[counter] = data;
				counter = counter + 1;
			}
		}
	}
	void combine_element(int []arr, int size) {
		counter = 1;
		arrange(arr, size, size - 1);
	}


	public static void Main(String[] args) {

		MyArray obj = new MyArray();

		int[] arr = {
			5,
			4,
			1,
			3,
			5,
			5,
			3,
			1,
			2,
			2,
			4,
			3
		};
		//Get the size of array
		int size = arr.Length;


		Console.Write("  Before Combine \n");
		obj.print_data(arr, size);
		Console.Write("  After Combine \n");
		obj.combine_element(arr, size);
		obj.print_data(arr, size);

	}
}

Output

  Before Combine
  5  4  1  3  5  5  3  1  2  2  4  3
  After Combine
  5  5  5  4  4  1  1  3  3  3  2  2
<?php
/*
  Php Program
  Arrange array elements by occurrence sequence
*/
class MyArray {
	public $counter;

	function __construct() {
		$this->counter = 0;
	}
	//Print array elements

	public 	function print_data($arr, $size) {
		for ($i = 0; $i < $size; $i++) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	public 	function arrange($arr, $size, $index) {
		if ($index < 0) {
			return;
		}
		//Get element
		$data = $arr[$index];
		$this->arrange($arr, $size, $index - 1);
		for ($i = $this->counter; $i < $size && $this->counter < $size; ++$i) {
			if ($arr[$i] == $data) {
				//swap element value
				$arr[$i] = $arr[$this->counter];
				$arr[$this->counter] = $data;
				$this->counter = $this->counter + 1;
			}
		}
	}

	function combine_element($arr, $size) {
		$this->counter = 1;
		$this->arrange($arr, $size, $size - 1);
	}
};

function main() {
	$obj = new MyArray();
	$arr = array(5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3);
	//Get the size of array
	$size = count($arr);
	echo(" Before Combine \n");
	$obj->print_data($arr, $size);
	echo(" After Combine \n");
	$obj->combine_element($arr, $size);
	$obj->print_data($arr, $size);
}
main();

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 4 1 3 5 5 3 1 2 2 4 3
/*
 Node Js Program
 Arrange array elements by occurrence sequence
*/
class MyArray {
	;
	constructor() {
		this.counter = 0;
	}
	//Print array elements
	print_data(arr, size) {
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	arrange(arr, size, index) {
		if (index < 0) {
			return;
		}
		//Get element
		var data = arr[index];
		this.arrange(arr, size, index - 1);
		for (var i = this.counter; i < size && this.counter < size; ++i) {
			if (arr[i] == data) {
				//swap element value
				arr[i] = arr[this.counter];
				arr[this.counter] = data;
				this.counter = this.counter + 1;
			}
		}
	}
	combine_element(arr, size) {
		this.counter = 1;
		this.arrange(arr, size, size - 1);
	}
}

function main(args) {
	var obj = new MyArray();
	var arr = [5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3];
	//Get the size of array
	var size = arr.length;
	process.stdout.write(" Before Combine \n");
	obj.print_data(arr, size);
	process.stdout.write(" After Combine \n");
	obj.combine_element(arr, size);
	obj.print_data(arr, size);
}
main();

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 5 5 4 4 1 1 3 3 3 2 2
# Python 3 Program

# Arrange array elements by occurrence sequence
class MyArray :
	
	def __init__(self) :
		self.counter = 0
	
	# Print array elements
	def print_data(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i],end="")
			i += 1
		
		print(end="\n")
	
	def arrange(self, arr, size, index) :
		if (index < 0) :
			return
		
		data = arr[index]
		self.arrange(arr, size, index - 1)
		i = self.counter
		while (i < size and self.counter < size) :
			if (arr[i] == data) :
				# swap element value
				arr[i] = arr[self.counter]
				arr[self.counter] = data
				self.counter = self.counter + 1
			
			i += 1
		
	
	def combine_element(self, arr, size) :
		self.counter = 1
		self.arrange(arr, size, size - 1)
	

def main() :
	obj = MyArray()
	arr = [5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3]
	size = len(arr)
	print(" Before Combine ")
	obj.print_data(arr, size)
	print(" After Combine ")
	obj.combine_element(arr, size)
	obj.print_data(arr, size)


if __name__ == "__main__":
	main()

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 5 5 4 4 1 1 3 3 3 2 2
# Ruby Program 
# Arrange array elements by occurrence sequence
class MyArray 
	# Define the accessor and reader of class MyArray
    attr_reader :counter
    attr_accessor :counter
	def initialize() 
		@counter = 0
	end
	# Print array elements
	def print_data(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	def arrange(arr, size, index) 
		if (index < 0) 
			return
		end
		data = arr[index]
		self.arrange(arr, size, index - 1)
		i = @counter
		while (i < size and @counter < size) 
			if (arr[i] == data) 
				# swap element value
				arr[i] = arr[@counter]
				arr[@counter] = data
				@counter = @counter + 1
			end
			i += 1
		end
	end
	def combine_element(arr, size) 
		@counter = 1
		self.arrange(arr, size, size - 1)
	end
end
def main() 
	obj = MyArray.new()
	arr = [5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3]
	size = arr.length
	print(" Before Combine \n")
	obj.print_data(arr, size)
	print(" After Combine \n")
	obj.combine_element(arr, size)
	obj.print_data(arr, size)
end


main()

Output

 Before Combine 
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine 
 5 5 5 4 4 1 1 3 3 3 2 2
/*
 Scala Program
 Arrange array elements by occurrence sequence
*/
class MyArray(var counter: Int) {
	
	def this() {
		this(0);
	}
	//Print array elements
	def print_data(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def arrange(arr: Array[Int], size: Int, index: Int): Unit = {
		if (index < 0) {
			return;
		}
		var data: Int = arr(index);
		this.arrange(arr, size, index - 1);
		var i: Int = this.counter;
		while (i < size && this.counter < size) {
			if (arr(i) == data) {
				//swap element value
				arr(i) = arr(this.counter);
				arr(this.counter) = data;
				this.counter = this.counter + 1;
			}
			i += 1;
		}
	}
	def combine_element(arr: Array[Int], size: Int): Unit = {
		this.counter = 1;this.arrange(arr, size, size - 1);
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		var arr: Array[Int] = Array(5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3);
		var size: Int = arr.length;
        print(" Before Combine \n");
        obj.print_data(arr, size);
        print(" After Combine \n");
        obj.combine_element(arr, size);
        obj.print_data(arr, size);
	}
}

Output

 Before Combine
 5 4 1 3 5 5 3 1 2 2 4 3
 After Combine
 5 5 5 4 4 1 1 3 3 3 2 2
/*
  Swift 4 Program
  Arrange array elements by occurrence sequence
*/
class MyArray {
	var counter : Int;
	init() {
		self.counter = 0;
	}
	//Print array elements
	func print_data(_ arr: [Int], _ size: Int) {
		var i: Int = 0;
		while (i < size) {
			print(" ", arr[i],terminator:"");
			i += 1;
		}
		print(terminator:"\n");
	}
	func arrange(_ arr: inout [Int], _ size: Int, _ index: Int) {
		if (index < 0) {
			return;
		}
		let data: Int = arr[index];
		self.arrange(&arr, size, index - 1);
		var i: Int = self.counter;
		while (i < size && self.counter < size) {
			if (arr[i] == data) {
				//swap element value
				arr[i] = arr[self.counter];
				arr[self.counter] = data;
				self.counter = self.counter + 1;
			}
			i += 1;
		}
	}
	func combine_element(_ arr: inout [Int], _ size: Int) {
		self.counter = 1;
		self.arrange(&arr, size, size - 1);
	}
}
func main() {
	let obj: MyArray = MyArray();
	var arr: [Int] = [5, 4, 1, 3, 5, 5, 3, 1, 2, 2, 4, 3];
	let size: Int = arr.count;
	print(" Before Combine");
	obj.print_data(arr, size);
	print(" After Combine ");
	obj.combine_element(&arr, size);
	obj.print_data(arr, size);
}
main();

Output

 Before Combine
  5  4  1  3  5  5  3  1  2  2  4  3
 After Combine
  5  5  5  4  4  1  1  3  3  3  2  2

Time Complexity

The recursive function runs for each element in the array and performs linear swaps. The time complexity of this algorithm is approximately O(n^2), where n is the size of the array.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment