Dado un entero positivo n, genere todas las formas únicas posibles de representar n como suma de enteros positivos.
Ejemplos:
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
Solución: Imprimimos todas las particiones en orden y los números dentro de una partición también se imprimen en orden (como se muestra en los ejemplos anteriores). La idea es obtener la siguiente partición utilizando los valores de la partición actual. Almacenamos cada partición en una array p[]. Inicializamos p[] como n donde n es el número de entrada. En cada iteración. primero imprimimos p[] y luego actualizamos p[] para almacenar la siguiente partición. Entonces, el problema principal es obtener la siguiente partición de una partición dada.
Pasos para obtener la siguiente partición de la partición actual:
Nos dan la partición actual en p[] y su tamaño. Necesitamos actualizar p[] para almacenar la siguiente partición. Los valores en p[] deben ordenarse en orden no creciente.
- Encuentre el valor no uno más a la derecha en p[] y almacene el conteo de 1 encontrado antes de un valor no uno en una variable rem_val (Indica la suma de valores en el lado derecho para actualizar). Sea k el índice de valor no uno.
- Disminuya el valor de p[k] en 1 y aumente rem_val en 1. Ahora puede haber dos casos:
- a) Si p[k] es mayor o igual que rem_val. Este es un caso simple (tenemos el orden ordenado en una nueva partición). Ponga rem_val en p[k+1] y p[0…k+1] es nuestra nueva partición.
- b) De lo contrario (este es un caso interesante, tome p[] inicial como {3, 1, 1, 1}, p[k] disminuye de 3 a 2, rem_val aumenta de 3 a 4, divida rem_val en diferentes valores de tamaño p[k] y copie estos valores en diferentes posiciones después de p[k], por lo que la siguiente partición debería ser {2, 2, 2}).
- Copie p[k] a la siguiente posición, incremente k y reduzca la cuenta en p[k] mientras que p[k] es menor que rem_val. Finalmente, coloque rem_val en p[k+1] y p[0…k+1] es nuestra nueva partición. Este paso es como dividir rem_val en términos de p[k] (4 se divide en 2).
La siguiente es la implementación del algoritmo anterior:
C++
// CPP program to generate all unique
// partitions of an integer
#include<iostream>
using namespace std;
// A utility function to print an array p[] of size '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]; // An array to store a partition
int k = 0; // Index of last element in a partition
p[k] = n; // Initialize first partition as number itself
// This loop first prints current partition then generates next
// partition. The loop stops when the current partition has all 1s
while (true)
{
// print current partition
printArray(p, k+1);
// Generate next partition
// Find the rightmost non-one value in p[]. Also, update the
// rem_val so that we know how much value can be accommodated
int rem_val = 0;
while (k >= 0 && p[k] == 1)
{
rem_val += p[k];
k--;
}
// if k < 0, all the values are 1 so there are no more partitions
if (k < 0) return;
// Decrease the p[k] found above and adjust the rem_val
p[k]--;
rem_val++;
// If rem_val is more, then the sorted order is violated. Divide
// rem_val in different values of size p[k] and copy these values at
// different positions after p[k]
while (rem_val > p[k])
{
p[k+1] = p[k];
rem_val = rem_val - p[k];
k++;
}
// Copy rem_val to next position and increment position
p[k+1] = rem_val;
k++;
}
}
// Driver program to test above functions
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
// Java program to generate all unique
// partitions of an integer
import java.io.*;
class GFG
{
// Function to print an array p[] of size n
static void printArray(int p[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(p[i]+" ");
System.out.println();
}
// Function to generate all unique partitions of an integer
static void printAllUniqueParts(int n)
{
int[] p = new int[n]; // An array to store a partition
int k = 0; // Index of last element in a partition
p[k] = n; // Initialize first partition as number itself
// This loop first prints current partition then generates next
// partition. The loop stops when the current partition has all 1s
while (true)
{
// print current partition
printArray(p, k+1);
// Generate next partition
// Find the rightmost non-one value in p[]. Also, update the
// rem_val so that we know how much value can be accommodated
int rem_val = 0;
while (k >= 0 && p[k] == 1)
{
rem_val += p[k];
k--;
}
// if k < 0, all the values are 1 so there are no more partitions
if (k < 0) return;
// Decrease the p[k] found above and adjust the rem_val
p[k]--;
rem_val++;
// If rem_val is more, then the sorted order is violated. Divide
// rem_val in different values of size p[k] and copy these values at
// different positions after p[k]
while (rem_val > p[k])
{
p[k+1] = p[k];
rem_val = rem_val - p[k];
k++;
}
// Copy rem_val to next position and increment position
p[k+1] = rem_val;
k++;
}
}
// Driver program
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);
}
}
// Contributed by Pramod Kumar
Python3
# A utility function to print an
# array p[] of size 'n'
def printArray(p, n):
for i in range(0, n):
print(p[i], end = " ")
print()
def printAllUniqueParts(n):
p = [0] * n # An array to store a partition
k = 0 # Index of last element in a partition
p[k] = n # Initialize first partition
# as number itself
# This loop first prints current partition,
# then generates next partition.The loop
# stops when the current partition has all 1s
while True:
# print current partition
printArray(p, k + 1)
# Generate next partition
# Find the rightmost non-one value in p[].
# Also, update the rem_val so that we know
# how much value can be accommodated
rem_val = 0
while k >= 0 and p[k] == 1:
rem_val += p[k]
k -= 1
# if k < 0, all the values are 1 so
# there are no more partitions
if k < 0:
print()
return
# Decrease the p[k] found above
# and adjust the rem_val
p[k] -= 1
rem_val += 1
# If rem_val is more, then the sorted
# order is violated. Divide rem_val in
# different values of size p[k] and copy
# these values at different positions after p[k]
while rem_val > p[k]:
p[k + 1] = p[k]
rem_val = rem_val - p[k]
k += 1
# Copy rem_val to next position
# and increment position
p[k + 1] = rem_val
k += 1
# Driver Code
print('All Unique Partitions of 2')
printAllUniqueParts(2)
print('All Unique Partitions of 3')
printAllUniqueParts(3)
print('All Unique Partitions of 4')
printAllUniqueParts(4)
# This code is contributed
# by JoshuaWorthington
C#
// C# program to generate all unique
// partitions of an integer
using System;
class GFG {
// Function to print an array p[]
// of size n
static void printArray(int []p, int n)
{
for (int i = 0; i < n; i++)
Console.Write(p[i]+" ");
Console.WriteLine();
}
// Function to generate all unique
// partitions of an integer
static void printAllUniqueParts(int n)
{
// An array to store a partition
int[] p = new int[n];
// Index of last element in a
// partition
int k = 0;
// Initialize first partition as
// number itself
p[k] = n;
// This loop first prints current
// partition, then generates next
// partition. The loop stops when
// the current partition has all 1s
while (true)
{
// print current partition
printArray(p, k+1);
// Generate next partition
// Find the rightmost non-one
// value in p[]. Also, update
// the rem_val so that we know
// how much value can be
// accommodated
int rem_val = 0;
while (k >= 0 && p[k] == 1)
{
rem_val += p[k];
k--;
}
// if k < 0, all the values are 1 so
// there are no more partitions
if (k < 0)
return;
// Decrease the p[k] found above
// and adjust the rem_val
p[k]--;
rem_val++;
// If rem_val is more, then the sorted
// order is violated. Divide rem_val in
// different values of size p[k] and copy
// these values at different positions
// after p[k]
while (rem_val > p[k])
{
p[k+1] = p[k];
rem_val = rem_val - p[k];
k++;
}
// Copy rem_val to next position and
// increment position
p[k+1] = rem_val;
k++;
}
}
// Driver program
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);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to generate
// all unique partitions
// of an integer
// A utility function to
// print an array p[] of
// size 'n'
function printArray( $p, $n)
{
for ($i = 0; $i < $n; $i++)
echo $p[$i] , " ";
echo "\n";
}
function printAllUniqueParts($n)
{
// An array to store
// a partition
$p[$n] = array(0);
// Index of last element
// in a partition
$k = 0;
// Initialize first
// partition as number
// itself
$p[$k] = $n;
// This loop first prints
// current partition, then
// generates next partition.
// The loop stops when the
// current partition has all 1s
while (true)
{
// print current partition
printArray($p, $k + 1);
// Generate next partition
// Find the rightmost non-one
// value in p[]. Also, update
// the rem_val so that we know
// how much value can be accommodated
$rem_val = 0;
while ($k >= 0 && $p[$k] == 1)
{
$rem_val += $p[$k];
$k--;
}
// if k < 0, all the values
// are 1 so there are no
// more partitions
if ($k < 0) return;
// Decrease the p[k] found
// above and adjust the
// rem_val
$p[$k]--;
$rem_val++;
// If rem_val is more, then
// the sorted order is violated.
// Divide rem_val in different
// values of size p[k] and copy
// these values at different
// positions after p[k]
while ($rem_val > $p[$k])
{
$p[$k + 1] = $p[$k];
$rem_val = $rem_val - $p[$k];
$k++;
}
// Copy rem_val to next
// position and increment
// position
$p[$k + 1] = $rem_val;
$k++;
}
}
// Driver Code
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);
// This code is contributed
// by akt_mit
?>
Javascript
<script>
// Javascript program to generate all unique
// partitions of an integer
// Function to print an array p[]
// of size n
function printArray(p, n)
{
for(let i = 0; i < n; i++)
document.write(p[i] + " ");
document.write("</br>");
}
// Function to generate all unique
// partitions of an integer
function printAllUniqueParts(n)
{
// An array to store a partition
let p = new Array(n);
// Index of last element in a
// partition
let k = 0;
// Initialize first partition as
// number itself
p[k] = n;
// This loop first prints current
// partition, then generates next
// partition. The loop stops when
// the current partition has all 1s
while (true)
{
// print current partition
printArray(p, k + 1);
// Generate next partition
// Find the rightmost non-one
// value in p[]. Also, update
// the rem_val so that we know
// how much value can be
// accommodated
let rem_val = 0;
while (k >= 0 && p[k] == 1)
{
rem_val += p[k];
k--;
}
// If k < 0, all the values are 1 so
// there are no more partitions
if (k < 0)
return;
// Decrease the p[k] found above
// and adjust the rem_val
p[k]--;
rem_val++;
// If rem_val is more, then the sorted
// order is violated. Divide rem_val in
// different values of size p[k] and copy
// these values at different positions
// after p[k]
while (rem_val > p[k])
{
p[k + 1] = p[k];
rem_val = rem_val - p[k];
k++;
}
// Copy rem_val to next position and
// increment position
p[k + 1] = rem_val;
k++;
}
}
// Driver code
document.write("All Unique Partitions of 2" + "</br>");
printAllUniqueParts(2);
document.write("All Unique Partitions of 3" + "</br>");
printAllUniqueParts(3);
document.write("All Unique Partitions of 4" + "</br>");
printAllUniqueParts(4);
// This code is contributed by divyesh072019
</script>
Producción:
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
Complejidad temporal: O(n * k)
Espacio auxiliar: O(n)
Este artículo es una contribución de Hariprasad NG . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA