prolog programming (3) Write programs to generate the nert higher permutation of

Question

prolog programming

(3) Write programs to generate the nert higher permutation of a list of positive integers, in two ways: (a) By applying the following definition of the problem: Permutation L1 is is the neact higher permutation of Lif L1 is a higher permutation of L and L1 is not far higher than L. (hint: use the built-in predicate not L1 is a higher permutation of L if it is a permutation of Land is higher than L. L1 is higher than Lif there is a left,most element of L1 that is greater than the leftmost element of L. (below, L1 higher than L in both pairs (e.g. L 4,2, 5, 3l; L1 5,2, 4, 3 L 5, 2, 3, 41; L1 JI5, 2, 4, 31. L1 is far higher than Lif there is a higher permutation L2 of L such that L1 is higher than L2.

Explanation / Answer

(b) Code in C++ :

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

// Utility function to swap two digits
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int[] findNext(int number[], int n)
{
int i, j;

// We start from the right side of the array and find the first digit that is
// smaller than the digit right to it.
for (i = n-1; i > 0; i--)
if (number[i] > number[i-1])
break;

// If no such digit is found, then it means all digits are sorted in descending order e.g. 4,3,2,1.
// In such a case, we cannot have any no. that is smaller than the no. to its right.
// So no permutation is possible for next higher no. and hence we return.
if (i==0)
{
cout << "Decreasing order and hence next higher number permutation is not possible";
return number;
}

// II) Find the smallest digit on right side of R that is
// greater than number R . e.g L= [1 2 3 5 4 2], R=3 is found in above loop.
// now we find the smallest no. in right side of R which is greater than R, i.e. X= 4
int x = number[i-1], smallest = i;
for (j = i+1; j < n; j++)
if (number[j] > x && number[j] < number[smallest])
smallest = j;

// after the smallest no. greater than R is found we call the swap method to swap them
swap(&number[smallest], &number[i-1]);

// According to question, the digits after X = 4 are reversed, i.e. , L = [1 2 4 5 3 2] => [1 2 4 2 3 5]
// this actually means that the digits after X (i.e. 4 ) must be in increasing order
// So here we sort the digits after X in increasing order.
sort(number + i, number + n);

cout << "Next permutation higher than given no. is " << number;

return number;
}

(a) For part (a) in question: According to my understanding, this definition/explaination is not for generating next higher permutation of a list of integers, rather it is for checking if two permutations are given then whether one is next higher permutation of the the other or not.

Code for this is :

boolean checkNextHigherPermutationOrNot(int l[], int l1[]) {

boolean flag = false;
// first we check if l1 is a permutation of l or not
//i.e. we check if l1 contains digits same as that of l.
if (!checkIfPermutation(l, l1)) {
return false;
}
//now we check if l1 is greater than l or not
// if it is not greater than l then it means that it is not a higher permutation of l
// so we return false
for (int i = 0; i < l.length; i++) {
if (l1[i] > l[i])
flag = true;
else
flag = false;
}
//now if it is a higher permutation then flag = true
//so here we check that if l1 is greater than the next higher permutation of l
// we call the same findNext function as above in part (b)
// if l1 is greater than next higher permutation of l then it means it is far higher permutation of l.
if(flag){
int next[] = findNext(l,l.length);
  
for (int i = 0; i < next.length; i++) {
if (l1[i] > next[i]){
flag = true;
cout<<"This is far higher permutation"
}
}
}
return flag;
}

boolean checkIfPermutation(int[] l, int[] l1) {
boolean flag = false;
if (l == null || l1 == null){
return false;
}
if(l.length != l1.length)
return false;
for(int i =0; i<l.length; i++){
for(int j =0; j<l1.length; i++){
if(l1[j] == l[i]){
flag=true;
}
}
if(!flag)
return false;
}
return flag;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.