Number of ways to arrange N items under given constraints

19 June 2025

0

We are given N items which are of total K different colors. Items of the same color are indistinguishable and colors can be numbered from 1 to K and count of items of each color is also given as k1, k2, and so on. Now we need to arrange these items one by one under the constraint that the last item of color i comes before the last item of color (i + 1) for all possible colors. Our goal is to find out how many ways this can be achieved.

Examples:

Input : N = 3        
        k1 = 1    k2 = 2
Output : 2
Explanation :
Possible ways to arrange are,
k1, k2, k2
k2, k1, k2 

Input : N = 4        
        k1 = 2    k2 = 2
Output : 3
Explanation :
Possible ways to arrange are,
k1, k2, k1, k2
k1, k1, k2, k2
k2, k1, k1, k2

Method 1:

We can solve this problem using dynamic programming. Let dp[i] stores the number of ways to arrange first i colored items. For one colored item answer will be one because there is only one way. Now Let’s assume all items are in a sequence. Now, to go from dp[i] to dp[i + 1], we need to put at least one item of color (i + 1) at the very end, but the other items of color (i + 1) can go anywhere in the sequence. The number of ways to arrange the item of color (i + 1) is combination of (k1 + k2 .. + ki + k(i + 1) – 1) over (k(i + 1) – 1) which can be represented as (k1 + k2 .. + ki + k(i + 1) – 1)C(k(i + 1) – 1). In this expression we subtracted one because we need to put one item at the very end.

In the below code, first, we have calculated the combination values, you can read more about that from here. After that we looped over all the different colors and calculated the final value using the above relation.

C++

// C++ program to find number of ways to arrange
// items under given constraint
#include <bits/stdc++.h>
using namespace std;
 
// method returns number of ways with which items 
// can be arranged
int waysToArrange(int N, int K, int k[])
{
    int C[N + 1][N + 1];
    int i, j;
 
    // Calculate value of Binomial Coefficient in 
    // bottom up manner
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= i; j++) {
 
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously 
            // stored values
            else
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);
        }
    }
 
    // declare dp array to store result up to ith 
    // colored item
    int dp[K];
 
    // variable to keep track of count of items 
    // considered till now
    int count = 0;
 
    dp[0] = 1;
 
    // loop over all different colors
    for (int i = 0; i < K; i++) {
 
        // populate next value using current value 
        // and stated relation
        dp[i + 1] = (dp[i] * C[count + k[i] - 1][k[i] - 1]);
        count += k[i];
    }
 
    // return value stored at last index
    return dp[K];
}
 
// Driver code to test above methods
int main()
{
    int N = 4;
    int k[] = { 2, 2 };
 
    int K = sizeof(k) / sizeof(int);
    cout << waysToArrange(N, K, k) << endl;
    return 0;
}

Java

// Java program to find number of ways to arrange
// items under given constraint
import java.io.*;
class GFG {
 
    // method returns number of ways with which items
    // can be arranged
    static int waysToArrange(int N, int K, int[] k)
    {
        int[][] C = new int[N + 1][N + 1];
        int i, j;
 
        // Calculate value of Binomial Coefficient in
        // bottom up manner
        for (i = 0; i <= N; i++) {
            for (j = 0; j <= i; j++) {
 
                // Base Cases
                if (j == 0 || j == i) {
                    C[i][j] = 1;
                }
 
                // Calculate value using previously
                // stored values
                else {
                    C[i][j]
                        = (C[i - 1][j - 1] + C[i - 1][j]);
                }
            }
        }
 
        // declare dp array to store result up to ith
        // colored item
        int[] dp = new int[K + 1];
 
        // variable to keep track of count of items
        // considered till now
        int count = 0;
 
        dp[0] = 1;
 
        // loop over all different colors
        for (i = 0; i < K; i++) {
 
            // populate next value using current value
            // and stated relation
            dp[i + 1]
                = (dp[i] * C[count + k[i] - 1][k[i] - 1]);
            count += k[i];
        }
 
        // return value stored at last index
        return dp[K];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 4;
        int[] k = new int[] { 2, 2 };
        int K = k.length;
        System.out.println(waysToArrange(N, K, k));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to find number of ways 
# to arrange items under given constraint
import numpy as np
 
# method returns number of ways with 
# which items can be arranged
def waysToArrange(N, K, k) :
 
    C = np.zeros((N + 1, N + 1))
 
    # Calculate value of Binomial 
    # Coefficient in bottom up manner
    for i in range(N + 1) :
        for j in range(i + 1) :
 
            # Base Cases
            if (j == 0 or j == i) :
                C[i][j] = 1
 
            # Calculate value using previously 
            # stored values
            else :
                C[i][j] = (C[i - 1][j - 1] +
                           C[i - 1][j])
 
    # declare dp array to store result 
    # up to ith colored item
    dp = np.zeros((K + 1))
 
    # variable to keep track of count 
    # of items considered till now
    count = 0
 
    dp[0] = 1
 
    # loop over all different colors
    for i in range(K) :
 
        # populate next value using current 
        # value and stated relation
        dp[i + 1] = (dp[i] * C[count + k[i] - 1][k[i] - 1])
        count += k[i]
     
    # return value stored at last index
    return dp[K]
 
# Driver code
if __name__ == "__main__" :
 
    N = 4
    k = [ 2, 2 ]
 
    K = len(k)
    print(int(waysToArrange(N, K, k)))
 
# This code is contributed by Ryuga 

C#

// C# program to find number of ways to arrange 
// items under given constraint 
using System; 
 
class GFG 
{ 
    // method returns number of ways with which items 
    // can be arranged 
    static int waysToArrange(int N, int K, int[] k) 
    { 
        int[,] C = new int[N + 1, N + 1]; 
        int i, j; 
     
        // Calculate value of Binomial Coefficient in 
        // bottom up manner 
        for (i = 0; i <= N; i++)  
        { 
            for (j = 0; j <= i; j++)
            { 
     
                // Base Cases 
                if (j == 0 || j == i) 
                    C[i, j] = 1; 
     
                // Calculate value using previously 
                // stored values 
                else
                    C[i, j] = (C[i - 1, j - 1] + C[i - 1,  j]); 
            } 
        } 
     
        // declare dp array to store result up to ith 
        // colored item 
        int[] dp = new int[K + 1]; 
     
        // variable to keep track of count of items 
        // considered till now 
        int count = 0; 
     
        dp[0] = 1; 
     
        // loop over all different colors 
        for (i = 0; i < K; i++) { 
     
            // populate next value using current value 
            // and stated relation 
            dp[i + 1] = (dp[i] * C[count + k[i] - 1, k[i] - 1]); 
            count += k[i]; 
        } 
     
        // return value stored at last index 
        return dp[K]; 
    } 
     
    // Driver code  
    static void Main() 
    { 
        int N = 4; 
        int[] k = new int[]{ 2, 2 }; 
        int K = k.Length; 
        Console.Write(waysToArrange(N, K, k)); 
    }
}
 
// This code is contributed by DrRoot_

PHP

<?php
// PHP program to find number of 
// ways to arrange items under 
// given constraint 
 
// method returns number of ways 
// with which items can be arranged 
function waysToArrange($N, $K, $k) 
{ 
    $C[$N + 1][$N + 1] = array(array()); 
     
    // Calculate value of Binomial  
    // Coefficient in bottom up manner 
    for ($i = 0; $i <= $N; $i++) 
    { 
        for ($j = 0; $j <= $i; $j++)
        { 
 
            // Base Cases 
            if ($j == 0 || $j == $i) 
                $C[$i][$j] = 1; 
 
            // Calculate value using 
            // previously stored values 
            else
                $C[$i][$j] = ($C[$i - 1][$j - 1] + 
                              $C[$i - 1][$j]); 
        } 
    } 
 
    // declare dp array to store 
    // result up to ith colored item 
    $dp[$K] = array(); 
 
    // variable to keep track of count 
    // of items considered till now 
    $count = 0; 
 
    $dp[0] = 1; 
 
    // loop over all different colors 
    for ($i = 0; $i < $K; $i++)
    { 
 
        // populate next value using 
        // current value and stated relation 
        $dp[$i + 1] = ($dp[$i] * $C[$count + 
                        $k[$i] - 1][$k[$i] - 1]); 
        $count += $k[$i]; 
    } 
 
    // return value stored at 
    // last index 
    return $dp[$K]; 
} 
 
// Driver code 
$N = 4; 
$k = array( 2, 2 ); 
 
$K = sizeof($k); 
echo waysToArrange($N, $K, $k),"\n"; 
 
// This code is contributed by jit_t
?>

Javascript

<script>
// Javascript program to find number of ways to arrange 
// items under given constraint.
 
    // method returns number of ways with which items 
    // can be arranged 
    function waysToArrange(N, K, k) 
    {
        let C = new Array(N + 1);
        // Loop to create 2D array using 1D array
        for (let i = 0; i < C.length; i++) {
            C[i] = new Array(2);
        }
         
        let i, j;
   
        // Calculate value of Binomial Coefficient in 
        // bottom up manner 
        for (i = 0; i <= N; i++) 
        {
            for (j = 0; j <= i; j++) 
            {
   
                // Base Cases 
                if (j == 0 || j == i) 
                {
                    C[i][j] = 1;
                } 
                   
                // Calculate value using previously 
                // stored values 
                else
                {
                    C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);
                }
            }
        }
   
        // declare dp array to store result up to ith 
        // colored item 
        let dp = Array.from({length: K+1}, (_, i) => 0);
   
        // variable to keep track of count of items 
        // considered till now 
        let count = 0;
   
        dp[0] = 1;
   
        // loop over all different colors 
        for (i = 0; i < K; i++) 
        {
   
            // populate next value using current value 
            // and stated relation 
            dp[i + 1] = (dp[i] * C[count + k[i] - 1][k[i] - 1]);
            count += k[i];
        }
   
        // return value stored at last index 
        return dp[K];
    }
   
// driver function
 
        let N = 4;
        let k = [2, 2];
        let K = k.length;
        document.write(waysToArrange(N, K, k));
   
</script>    

Output

Time Complexity: O(N²)
Auxiliary space: O(N*N)

This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Number of ways to arrange N items under given constraints

C++

Java

Python3

C#

PHP

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

007 First Light seems like it offers exactly what I want from a James Bond video game

The biggest name on YouTube wants to run your next cell network

Google’s Android 16 QPR1 arrives with a fresh coat of paint for Pixel 6 and later

You’ll soon be able to answer calls on your Pixel Buds Pro 2 simply by nodding your head

EDITOR PICKS

007 First Light seems like it offers exactly what I want from a James Bond video game

The biggest name on YouTube wants to run your next cell network

Google’s Android 16 QPR1 arrives with a fresh coat of paint for Pixel 6 and later

POPULAR POSTS

007 First Light seems like it offers exactly what I want from a James Bond video game

The biggest name on YouTube wants to run your next cell network

Google’s Android 16 QPR1 arrives with a fresh coat of paint for Pixel 6 and later

POPULAR CATEGORY

ABOUT US

FOLLOW US