IN C++ PLEASE We list the r-combinations of {1, 2, . . . , n} in lexicographic order and represent an r-combination of {1, 2, . . . , n} by a sequence that contains the numbers of the r-combination in increasing order. We begin with {1, 2, . . . , r}, and the procedure for finding the next r-combination after {a1, a2, . . . , ar} is given by the following algorithm: 1. Find the last member ai of the sequence {a1, a2, . . . , ar} such that n − r + i 6= ai. Stop if ai does not exist. 2. Replace ai by ai + 1 . 3. For each j = i + 1, i + 2, . . . , r, replace aj by aj−1 + 1. 4. Go to step 1. EXAMPLE List the 3-combinations of {1, 2, 3, 4, 5} in lexicographic order. Analysis We begin with {1, 2, 3}. We are listing the 3-combinations, so a1 = 1, a2 = 2, and a3 = 3. Now n − r + 3 = 5, and 5 6= a3. Therefore we replace a3 with a3 + 1 = 4 and obtain {1, 2, 4} as the next 3-combination. We have a1 = 1, a2 = 2, and a3 = 4, so n − r + 3 = 5, and 5 6= a3. Therefore we replace a3 with a3 + 1 = 5 and obtain {1, 2, 5} as the next 3-combination. We have a1 = 1, a2 = 2, and a3 = 5. Since n − r + 3 = 5 and 5 = a3, but n − r + 2 = 4 and 4 6= a2, we replace a2 with a2 + 1 = 3 and a3 by a2 + 1 = 3 + 1 = 4 and obtain {1, 3, 4} as the next 3-combination. Continuing in this manner, we obtain the following ordering of the 3-combinations. {1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} {2, 3, 5} {2, 4, 5} {3, 4, 5}
IN C++ PLEASE
We list the r-combinations of {1, 2, . . . , n} in lexicographic order and represent an r-combination of {1, 2, . . . , n} by a sequence that contains the numbers of the r-combination in increasing order. We begin with {1, 2, . . . , r}, and the procedure for finding the next r-combination after {a1, a2, . . . , ar} is given by the following
1. Find the last member
2. Replace ai by ai + 1 .
3. For each j = i + 1, i + 2, . . . , r, replace aj by aj−1 + 1.
4. Go to step 1.
EXAMPLE List the 3-combinations of {1, 2, 3, 4, 5} in lexicographic order.
Analysis
We begin with {1, 2, 3}. We are listing the 3-combinations, so a1 = 1, a2 = 2, and a3 = 3. Now n − r + 3 = 5, and 5 6= a3. Therefore we replace a3 with a3 + 1 = 4 and obtain {1, 2, 4} as the next 3-combination. We have a1 = 1, a2 = 2, and a3 = 4, so n − r + 3 = 5, and 5 6= a3. Therefore we replace a3 with a3 + 1 = 5 and obtain {1, 2, 5} as the next 3-combination. We have a1 = 1, a2 = 2, and a3 = 5. Since n − r + 3 = 5 and 5 = a3, but n − r + 2 = 4 and 4 6= a2, we replace a2 with a2 + 1 = 3 and a3 by a2 + 1 = 3 + 1 = 4 and obtain {1, 3, 4} as the next 3-combination. Continuing in this manner, we obtain the following ordering of the 3-combinations.
{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 3, 4}
{1, 3, 5}
{1, 4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{3, 4, 5}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
