Рубрики

Генерация всех уникальных разделов целого числа

Учитывая положительное целое число n, сгенерируйте все возможные уникальные способы представления n в виде суммы натуральных чисел.
Примеры:

  Input: n = 2
  Output: 
  2
  1 1

  Input: n = 3
  Output: 
  3
  2 1
  1 1 1
  Note: 2+1 and 1+2 are considered as duplicates.

  Input: n = 4
  Output: 
  4
  3 1
  2 2
  2 1 1
  1 1 1 1 

Решение: Мы печатаем все разделы в отсортированном порядке, а номера внутри раздела также печатаются в отсортированном порядке (как показано в приведенных выше примерах). Идея состоит в том, чтобы получить следующий раздел, используя значения в текущем разделе. Мы храним каждый раздел в массиве p []. Мы инициализируем p [] как n, где n — номер ввода. На каждой итерации. сначала мы печатаем p [], а затем обновляем p [], чтобы сохранить следующий раздел. Таким образом, основная проблема состоит в том, чтобы получить следующий раздел из данного раздела.

Шаги, чтобы получить следующий раздел из текущего раздела:
Нам дан текущий раздел в p [] и его размер. Нам нужно обновить p [], чтобы сохранить следующий раздел. Значения в p [] должны быть отсортированы в порядке возрастания.

  1. Найдите самое правое не одно значение в p [] и сохраните количество единиц, встречающихся перед не одним значением, в переменной rem_val (она указывает сумму значений на правой стороне, которая будет обновлена). Пусть индекс не одного значения будет k.
  2. Уменьшите значение p [k] на 1 и увеличьте rem_val на 1. Теперь может быть два случая:
    • а) если
    • p [k] больше или равно rem_val. Это простой случай (у нас есть отсортированный порядок в новом разделе). Поместите rem_val в p [k + 1], а p [0… k + 1] — наш новый раздел.

  3. б) Иначе (это интересный случай, примите начальное p [], поскольку {3, 1, 1, 1}, p [k] уменьшено с 3 до 2, rem_val увеличено с 3 до 4, следующий раздел должен быть {2, 2, 2}).
  4. Скопируйте p [k] в следующую позицию, увеличьте k и уменьшите счет на p [k], пока p [k] меньше чем rem_val. Наконец, поместите rem_val в p [k + 1], а p [0… k + 1] — наш новый раздел. Этот шаг похож на деление rem_val в терминах p [k] (4 делится на 2).

Ниже приведена реализация вышеуказанного алгоритма:

C / C ++

// Программа CPP для генерации всего уникального
// разделы целого числа
#include<iostream>

using namespace std;

  
// Вспомогательная функция для печати массива p [] размера 'n'

void printArray(int p[], int n)

{

    for (int i = 0; i < n; i++)

       cout << p[i] << " ";

    cout << endl;

}

  

void printAllUniqueParts(int n)

{

    int p[n]; // Массив для хранения раздела

    int k = 0;  // Индекс последнего элемента в разделе

    p[k] = n;  // Инициализируем первый раздел как само число

  

    // Этот цикл сначала печатает текущий раздел, а затем генерирует следующий

    // раздел. Цикл останавливается, когда текущий раздел имеет все 1 с

    while (true)

    {

        // распечатать текущий раздел

        printArray(p, k+1);

  

        // Создать следующий раздел

  

        // Находим самое правое не одно значение в p []. Кроме того, обновите

        // rem_val, чтобы мы знали, сколько можно разместить

        int rem_val = 0;

        while (k >= 0 && p[k] == 1)

        {

            rem_val += p[k];

            k--;

        }

  

        // если k <0, все значения равны 1, поэтому разделов больше нет

        if (k < 0)  return;

  

        // Уменьшаем найденное выше p [k] и корректируем rem_val

        p[k]--;

        rem_val++;

  

  

        // Если rem_val больше, то отсортированный порядок нарушается. Делить

        // rem_val в различных значениях размера p [k] и копируем эти значения в

        // разные позиции после p [k]

        while (rem_val > p[k])

        {

            p[k+1] = p[k];

            rem_val = rem_val - p[k];

            k++;

        }

  

        // Копировать rem_val в следующую позицию и увеличить позицию

        p[k+1] = rem_val;

        k++;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    cout << "All Unique Partitions of 2 \n";

    printAllUniqueParts(2);

  

    cout << "\nAll Unique Partitions of 3 \n";

    printAllUniqueParts(3);

  

    cout << "\nAll Unique Partitions of 4 \n";

    printAllUniqueParts(4);

  

    return 0;

}

Джава

// Java программа для генерации всего уникального
// разделы целого числа

import java.io.*;

  

class GFG 

{

    // Функция для печати массива p [] размера n

    static void printArray(int p[], int n)

    {

        for (int i = 0; i < n; i++)

            System.out.print(p[i]+" ");

        System.out.println();

    }

      

    // Функция для генерации всех уникальных разделов целого числа

    static void printAllUniqueParts(int n)

    {

        int[] p = new int[n]; // Массив для хранения раздела

        int k = 0// Индекс последнего элемента в разделе

        p[k] = n;  // Инициализируем первый раздел как само число

   

        // Этот цикл сначала печатает текущий раздел, а затем генерирует следующий

        // раздел. Цикл останавливается, когда текущий раздел имеет все 1 с

        while (true)

        {

            // распечатать текущий раздел

            printArray(p, k+1);

   

            // Создать следующий раздел

   

            // Находим самое правое не одно значение в p []. Кроме того, обновите

            // rem_val, чтобы мы знали, сколько можно разместить

            int rem_val = 0;

            while (k >= 0 && p[k] == 1)

            {

                rem_val += p[k];

                k--;

            }

   

            // если k <0, все значения равны 1, поэтому разделов больше нет

            if (k < 0return;

   

            // Уменьшаем найденное выше p [k] и корректируем rem_val

            p[k]--;

            rem_val++;

   

   

            // Если rem_val больше, то отсортированный порядок нарушается. Делить

            // rem_val в различных значениях размера p [k] и копируем эти значения в

            // разные позиции после p [k]

            while (rem_val > p[k])

            {

                p[k+1] = p[k];

                rem_val = rem_val - p[k];

                k++;

            }

   

            // Копировать rem_val в следующую позицию и увеличить позицию

            p[k+1] = rem_val;

            k++;

        }

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        System.out.println("All Unique Partitions of 2");

        printAllUniqueParts(2);

          

        System.out.println("All Unique Partitions of 3");

        printAllUniqueParts(3);

          

        System.out.println("All Unique Partitions of 4");

        printAllUniqueParts(4);

    }

}

  
// Предоставлено Прамод Кумар

питон

# Утилита для печати
# массив p [] размера 'n'

def printArray(p, n):

    for i in range(0, n):

        print(p[i], end = " ")

    print()

  

def printAllUniqueParts(n):

    p = [0] * n     # Массив для хранения раздела

    k = 0         # Индекс последнего элемента в разделе

    p[k] = n     # Инициализировать первый раздел

                 # как само число

  

    # Этот цикл сначала печатает текущий раздел,

    # затем генерирует следующий раздел. Цикл

    # останавливается, когда текущий раздел имеет все 1

    while True:

          

            # распечатать текущий раздел

            printArray(p, k + 1)

  

            # Создать следующий раздел

  

            # Найти самое правое не одно значение в p [].

            # Также обновите rem_val, чтобы мы знали

            # сколько можно разместить

            rem_val = 0

            while k >= 0 and p[k] == 1:

                rem_val += p[k]

                k -= 1

  

            # если k <0, все значения равны 1, так

            # разделов больше нет

            if k < 0:

                print()

                return

  

            # Уменьшить найденное выше значение p [k]

            # и настройте rem_val

            p[k] -= 1

            rem_val += 1

  

            # Если rem_val больше, то отсортированный

            # порядок нарушен. Разделить rem_val в

            # разные значения размера p [k] и копии

            # эти значения в разных позициях после p [k]

            while rem_val > p[k]:

                p[k + 1] = p[k]

                rem_val = rem_val - p[k]

                k += 1

  

            # Копировать rem_val на следующую позицию

            # и позиция приращения

            p[k + 1] = rem_val

            k += 1

  
Код водителя

print('All Unique Partitions of 2')

printAllUniqueParts(2)

  

print('All Unique Partitions of 3')

printAllUniqueParts(3)

  

print('All Unique Partitions of 4')

printAllUniqueParts(4)

  
# Этот код добавлен
# от JoshuaWorthington

C #

// C # программа для генерации всего уникального
// разделы целого числа

using System;

  

class GFG {

      

    // Функция для печати массива p []

    // размера n

    static void printArray(int []p, int n)

    {

        for (int i = 0; i < n; i++)

            Console.Write(p[i]+" ");

              

        Console.WriteLine();

    }

      

    // Функция для генерации всего уникального

    // разделы целого числа

    static void printAllUniqueParts(int n)

    {

          

        // Массив для хранения раздела

        int[] p = new int[n]; 

          

        // Индекс последнего элемента в

        // раздел

        int k = 0; 

          

        // Инициализируем первый раздел как

        // сам номер

        p[k] = n; 

  

        // Этот цикл сначала печатает текущий

        // раздел, затем генерирует следующий

        // раздел. Цикл останавливается, когда

        // текущий раздел имеет все 1

        while (true)

        {

              

            // распечатать текущий раздел

            printArray(p, k+1);

  

            // Создать следующий раздел

  

            // Найти самый правый не один

            // значение в p []. Кроме того, обновить

            // rem_val, чтобы мы знали

            // сколько может стоить

            // размещены

            int rem_val = 0;

              

            while (k >= 0 && p[k] == 1)

            {

                rem_val += p[k];

                k--;

            }

  

            // если k <0, все значения равны 1, так

            // разделов больше нет

            if (k < 0) 

                return;

  

            // Уменьшаем найденное выше p [k]

            // и настроить rem_val

            p[k]--;

            rem_val++;

  

  

            // Если rem_val больше, то отсортированный

            // порядок нарушен. Разделить rem_val в

            // разные значения размера p [k] и копии

            // эти значения в разных позициях

            // после р [к]

            while (rem_val > p[k])

            {

                p[k+1] = p[k];

                rem_val = rem_val - p[k];

                k++;

            }

  

            // Копировать rem_val в следующую позицию и

            // увеличиваем позицию

            p[k+1] = rem_val;

            k++;

        }

    }

      

    // Драйвер программы

    public static void Main () 

    {

        Console.WriteLine("All Unique Partitions of 2");

        printAllUniqueParts(2);

          

        Console.WriteLine("All Unique Partitions of 3");

        printAllUniqueParts(3);

          

        Console.WriteLine("All Unique Partitions of 4");

        printAllUniqueParts(4);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для генерации
// все уникальные разделы
// целого числа

  
// Функция полезности для
// выводим массив p [] of
// размер 'n'

function printArray( $p, $n)

{

    for ($i = 0; $i < $n; $i++)

    echo $p[$i] , " ";

    echo "\n";

}

  

function printAllUniqueParts($n)

{

    // массив для хранения

    // раздел

    $p[$n] = array(0); 

      

    // Индекс последнего элемента

    // в разделе

    $k = 0; 

      

    // Сначала инициализируем

    // разделить как число

    // сам

    $p[$k] = $n

  

    // Этот цикл сначала печатает

    // текущий раздел, затем

    // генерирует следующий раздел.

    // цикл останавливается, когда

    // текущий раздел имеет все 1

    while (true)

    {

        // распечатать текущий раздел

        printArray($p, $k + 1);

  

        // Создать следующий раздел

  

        // Найти самый правый не один

        // значение в p []. Кроме того, обновить

        // rem_val, чтобы мы знали

        // сколько можно разместить

        $rem_val = 0;

        while ($k >= 0 && $p[$k] == 1)

        {

            $rem_val += $p[$k];

            $k--;

        }

  

        // если k <0, все значения

        // 1, поэтому нет

        // больше разделов

        if ($k < 0) return;

  

        // Уменьшаем найденное p [k]

        // выше и отрегулируйте

        // rem_val

        $p[$k]--;

        $rem_val++;

  

  

        // Если rem_val больше, то

        // отсортированный порядок нарушен.

        // Делим rem_val на разные

        // значения размера p [k] и копии

        // эти значения у разных

        // позиции после p [k]

        while ($rem_val > $p[$k])

        {

            $p[$k + 1] = $p[$k];

            $rem_val = $rem_val - $p[$k];

            $k++;

        }

  

        // Копировать rem_val в следующее

        // позиция и приращение

        // позиция

        $p[$k + 1] = $rem_val;

        $k++;

    }

}

  
// Код драйвера

echo "All Unique Partitions of 2 \n";

printAllUniqueParts(2);

  

echo "\nAll Unique Partitions of 3 \n";

printAllUniqueParts(3);

  

echo "\nAll Unique Partitions of 4 \n";

printAllUniqueParts(4);

  
// Этот код добавлен
// от akt_mit
?>


Выход:

All Unique Partitions of 2
2
1 1

All Unique Partitions of 3
3
2 1
1 1 1

All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1

Эта статья предоставлена Hariprasad NG . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Генерация всех уникальных разделов целого числа

0.00 (0%) 0 votes