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_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.

Categories
Relative Post