Problem Solving with C++ (10th Edition)
10th Edition
ISBN: 9780134448282
Author: Walter Savitch, Kenrick Mock
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
Chapter 14, Problem 8PP
Program Plan Intro
Finding all permutations for a set
Program Plan:
- Include required file.
- Define the structure for node.
- Declare elements in “vector” type.
- Declare variable for next value in “NodeValue” type.
- Declare function for display permutations.
- Declare function for compute permutations with recursively.
- Declare function for display vector elements of set.
- Define main function.
- Call the function “displayPermutations” with one parameter.
- Define function “displayPermutations”.
- Create a pointer for node.
- Declare the set in “vector” type.
- Fill the set with first “n” whole elements.
- Call the function “displayVectorElements” to print the
vectors . - Then compute the permutation for given set by calling the function “recursivePermutations”.
- Performs “while” loop. This loop executes until the pointer is equal to “NULL”.
- Display the values in set by calling the function “displayVectorElements”.
- Then delete and move to the next value.
- Define function “recursivePermutations”.
- This function is used to returns a list holding all of the permutations of the given list of elements.
- In this function, first assign the pointer list to “NULL”.
- Then performs base case if the size of the vector element is “1”. Otherwise performs recursive case.
- Compute the permutations for smaller set of elements by recursively call the function “recursivePermutations”.
- Define function “displayVectorElements”.
- This function is used to display the elements of set.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…
In chess, a walk for a particular piece is a sequence of legal moves for that piece, starting from a square of your choice, that visits every square of the board. A tour is a walk that visits every square only once. (See Figure 5.13.)
5.13 Prove by induction that there exists a knight’s walk of an n-by-n chessboard for any n ≥ 4. (It turns out that knight’s tours exist for all even n ≥ 6, but you don’t need to prove this fact.)
Algorithm design with sorting. Each of n users spends some time on a social media site. For each i = 1, . . . , n, user i enters the site at time ai and leaves at time bi ≥ ai. You are interested in the question: how many distinct pairs of users are ever on the site at the same time? (Here, the pair (i, j) is the same as the pair (j, i)).Example: Suppose there are 5 users with the following entering and leaving times:
Then, the number of distinct pairs of users who are on the site at the same time is five: these pairs are (1, 2), (1, 3), (2, 3), (4, 6), (5, 6). (Drawing the intervals on a number line may make this easier to see).(a) Given input (a1 , b1),(a2 , b2), . . . ,(an, bn) as above in no particular order (i.e., not sorted in any way), describe a straightforward algorithm that takes Θ(n2)-time to compute the number of pairs of users who are ever on the site at the same time, and explain why it takes Θ(n2)-time. [We are expecting pseudocode and a brief justification for its…
Chapter 14 Solutions
Problem Solving with C++ (10th Edition)
Ch. 14.1 - Prob. 1STECh. 14.1 - Prob. 2STECh. 14.1 - Prob. 3STECh. 14.1 - Prob. 4STECh. 14.1 - Prob. 5STECh. 14.1 - If your program produces an error message that...Ch. 14.1 - Write an iterative version of the function cheers...Ch. 14.1 - Write an iterative version of the function defined...Ch. 14.1 - Prob. 9STECh. 14.1 - Trace the recursive solution you made to Self-Test...
Ch. 14.1 - Trace the recursive solution you made to Self-Test...Ch. 14.2 - What is the output of the following program?...Ch. 14.2 - Prob. 13STECh. 14.2 - Redefine the function power so that it also works...Ch. 14.3 - Prob. 15STECh. 14.3 - Write an iterative version of the one-argument...Ch. 14 - Prob. 1PCh. 14 - Prob. 2PCh. 14 - Write a recursive version of the search function...Ch. 14 - Prob. 4PCh. 14 - Prob. 5PCh. 14 - The formula for computing the number of ways of...Ch. 14 - Write a recursive function that has an argument...Ch. 14 - Prob. 3PPCh. 14 - Prob. 4PPCh. 14 - Prob. 5PPCh. 14 - The game of Jump It consists of a board with n...Ch. 14 - Prob. 7PPCh. 14 - Prob. 8PP
Knowledge Booster
Similar questions
- The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence of distinct positive integers, the goal is to output the longest subsequence whose elements appear from smallest to largest, or from largest to smallest. For example, consider the sequence S = [9,7,4,10,6,8,2,1,3,5]. The longest increasing subsequence of S has length three ([4,6,8] or [2,3,5]), and the longest decreasing subsequence of S has length five([9,7,4,2,1] or [9,7,6,2,1]). And if we have the sequence S = [531,339,298,247,246,195,104,73,52,31], then the length of the longest increasing subsequence is 1 and the length of the longest decreasing subsequence is 10. Question: Let S be a sequence with ten distinct integers. Prove by Contradiction that there must exist an increasing subsequence of length 4 (or more) or a decreasing subsequence of length 4 (or more). Hint: for each integer k in the sequence you found in the first part, define the ordered pair (x(k), y(k)), where x(k)…arrow_forwardWrite the sets A and B if A - B = {1, 5, 7, 8}, B – A ={2, 10}, and A N B = {{3, 6, 9arrow_forwardFind the cardinal num ber for the following sets. A = {100, 101, 102, 103,..., 159} B = {100, 102, 104, ..., 150} n(A)=arrow_forward
- Implement a program that will populate a 6x5 matrix with randomly generated integers from 100 to 500. (1) print your matrix in a table form. (2) modify your code to multiply all odd numbers by 2 and print the matrix. Sample run: Initial Matrix: 145 | 437 | 222 | 101 | 100 | 278 500 | 190 | 415 | 288 | 466 322 377 | 240 | 451 | 331 186 186 432 102 | 106 | 105 249 248 | 117 | 213 | 499 488 355 | 266 | 396 | New Matrix: 290 | 874 | 222 | 101 | 100 | 278 500 | 190 | 830 288 | 466 322 754 | 240 | 902 | 662 186 432 | 102 | 106 | 210| 498 248 | 234 | 426 | 998 488 710 | 266 | 396 |arrow_forwardRecursive filtering techniques are often used to reduce the computational complexity of a repeated operation such as filtering. If an image filter is applied to each location in an image, a (horizontally) recursive formulation of the filtering operation expresses the result at location (x +1, y) in terms of the previously computed result at location (x, y). A box convolution filter, B, which has coefficients equal to one inside a rectangular win- dow, and zero elsewhere is given by: w-1h-1 B(r, y,w, h) = ΣΣΤ+ i,y + ) i=0 j=0 where I(r, y) is the pixel intensity of image I at (x, y). We can speed up the computation of arbitrary sized box filters using recursion as described above. In this problem, you will derive the procedure to do this. (a) The function J at location (x,y) is defined to be the sum of the pixel values above and to the left of (x,y), inclusive: J(r, y) = - ΣΣ14.0 i=0 j=0 Formulate a recursion to compute J(r, y). Assume that I(r, y) = 0 if r <0 or y < 0. Hint: It may be…arrow_forward1. Write an algorithm to determine whether a given element x belongs to a set S := {s1, . . . , sn}.arrow_forward
- Complete the task using the return search algorithm: Task: The labyrinth is represented by a Boolean square matrix A8x8. The cell (i, j) is considered passable if the element ai, j is true and otherwise impassable. Write a program that checks if there is a path from adjacent horizontally and vertically passable cells of the maze, which starts in its upper left corner (0.0) and ends in its lower right corner (7.7). Operating instructions: 1) Compose a Boolean function Path (i, j), called with initial parameters (0,0); 2) If cell (i, j) is outside the matrix Path returns false; 3) If cell (i, j) coincides with (7,7) a path is found and Path returns true; 4) If cell (i, j) is impassable Path returns false (because it cannot exit the cell), otherwise (if the cell is passable) there is a path from it to cell (7,7), if there is a path from any of the cells adjacent to (i, j) next to cell (7,7). Adjacent cells per cell (i, j) are cells (i + 1, j), (i, j + 1), (i-1, j), (i, j-1).arrow_forwardIn python, The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence of distinct positive integers, the goal is to output the longest subsequence whose elements appear from smallest to largest, or from largest to smallest. For example, consider the sequence S= [9,7,4,10,6,8,2,1,3,5]. The longest increasing subsequence of S has length three ([4,6,8] or [2,3,5]), and the longest decreasing subsequence of S has length five([9,7,4,2,1] or [9,7,6,2,1]). And if we have the sequence S = [531,339,298,247,246,195,104,73,52,31], then the length of the longest increasing subsequence is 1 and the length of the longest decreasing subsequence is 10. Question: Find a sequence with nine distinct integers for which the length of the longest increasing subsequence is 3, and the length of the longest decreasing subsequence is 3. Briefly explain how youconstructed your sequence.arrow_forwardCorrect answer will be upvoted else downvoted. Computer science. You are given an exhibit a comprising of n (n≥3) positive integers. It is realized that in this exhibit, every one of the numbers with the exception of one are something very similar (for instance, in the cluster [4,11,4,4] all numbers aside from one are equivalent to 4). Print the list of the component that doesn't rise to other people. The numbers in the cluster are numbered from one. Input The main line contains a solitary integer t (1≤t≤100). Then, at that point, t experiments follow. The main line of each experiment contains a solitary integer n (3≤n≤100) — the length of the exhibit a. The second line of each experiment contains n integers a1,a2,… ,an (1≤ai≤100). It is ensured that every one of the numbers aside from one in the an exhibit are something very similar. Output For each experiment, output a solitary integer — the list of the component that isn't equivalent to other people.arrow_forward
- Write an algorithm that uses an adjacency matrix, A[n][n], to determine if a digraph contains the back edge of one of its edges. (The back edge of an edge (i, j) is the edge (j, i).) 2.arrow_forwardCorrect answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science. each individual has a rating chart portrayed by a variety of integers an of length n. You are currently refreshing the foundation, so you've made a program to pack these diagrams. The program functions as follows. Given an integer boundary k, the program takes the base of each adjoining subarray of length k in a. All the more officially, for a cluster an of length n and an integer k, characterize the k-pressure exhibit of an as a cluster b of length n−k+1, to such an extent that bj=minj≤i≤j+k−1ai For instance, the 3-pressure cluster of [1,3,4,5,2] is [min{1,3,4},min{3,4,5},min{4,5,2}]=[1,3,2]. A stage of length m is an exhibit comprising of m unmistakable integers from 1 to m in subjective request. For instance, [2,3,1,5,4] is a stage, however [1,2,2] isn't a change (2 shows up twice in the exhibit) and [1,3,4] is likewise not a stage (m=3 but rather there is 4 in the…arrow_forwardA magic square is a square array of non-negative integers where the sums of the numbers on each row,each column, and both main diagonals are the same. An N × N occult square is a magic square with Nrows and N columns with additional constraints:• The integers in the square are between 0 and N, inclusive.• For all 1 ≤ i ≤ N, the number i appears at most i times in the square.• There are at least two distinct positive integers in the square.For example, the following is a 5 × 5 occult square, where the sums of the numbers on each row, eachcolumn, and both main diagonals are 7:0 0 0 3 42 4 0 0 10 0 3 4 05 0 0 0 20 3 4 0 0For a given prime number P, you are asked to construct a P × P occult square, or determine whether nosuch occult square exists.InputInput contains a prime number: P (2 ≤ P ≤ 1000) representing the number of rows and columns in theoccult square.OutputIf there is no P × P occult square, simply output -1 in a line. Otherwise, output P lines, each contains Pintegers…arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education