PART2K
PART2K is a DOS BASIC program to find partitions of a number n into all the integer parts that add up to that sum, with the optional constraints that all partitions have just m parts, that all parts are unique, and that all parts be <= p. It computes P(n), Q(n), P(n,m), and Q(n,m). I wrote this program to solve a problem that arises with with magic squares and other recreational math stumpers: what are all the ways in which m different numbers can add up to n, without regard to order? Partitioning is a bit like factoring in that it decomposes a number, but it uses addition rather than multiplication. This was a fun programming challenge that uses recursive functions.
Last update: 9 Jan 2000
View README.TXT
Download PART2K.ZIP (50K)
2 commentaires:
The Java code you provided generates all possible partitions of the
given number, from 1 to N terms (where N is the number itself).
You may use a List(Of Integer()) to store the output of the code. If
you only want the partitions with 4 terms, then you may copy only
those to another list. But if you want to treat partitions with the
same terms as equal regardless of the positions of those terms, then
you probably need a speciallized comparer for the partitions.
A possible solution follows. The method Partition1.GetPartitions
(Number) returns a List(Of Integer()) of all the partitions for that
given number. The auxiliary method SortPartitions then uses a
specialized comparer to create a list with only the unique partitions
with 4 terms:
example1
Sub Main()
Console.Write("Value: ")
Dim L As Integer = Convert.ToInt32(Console.ReadLine)
Do While L > 0
For Each I As Integer() _
In SortPartitions( _
Partition1.GetPartitions(L), 4)
For Each J As Integer In I
Console.Write("{0} ", J)
Next
Console.WriteLine
Next
Console.WriteLine
Console.Write("Value: ")
L = Convert.ToInt32(Console.ReadLine)
Loop
End Sub
Function SortPartitions( _
L As IList(Of Integer()), _
Count As Integer _
) As List(Of Integer())
Dim Cp As New PartitionComparer
Dim S As New List(Of Integer())
For Each I As Integer() In L
If I.Length = Count Then
Dim J As Integer = S.BinarySearch(I, Cp)
If J < 0 then S.Insert(J Xor -1, I)
End If
Next
Return S
End Function
Public Class Partition1
Private mList As List(Of Integer())
Public Function Partition( _
Value As Integer _
) As List(Of Integer())
Dim P(0 To Value-1) As Integer
Dim R As New List(Of Integer())
mList = R
DoPartition(P, Value, Value, 0)
mList = Nothing
Return R
End Function
Private Sub DoPartition( _
P() As Integer, _
N As Integer, _
M As Integer, _
I As Integer)
If N = 0 Then
Dim R(0 To I - 1) As Integer
Array.Copy(P, R, I)
mList.Add(R)
Else
For K As Integer = M To 1 Step-1
P(I) = K
DoPartition(P, N-K, N-K, I + 1)
Next
End If
End Sub
Public Shared Function GetPartitions( _
Value As Integer _
) As List(Of Integer())
Return New Partition1().Partition(Value)
End Function
End Class
Class PartitionComparer
Implements IComparer(Of Integer())
Public Function Compare( _
ByVal x() As Integer, _
ByVal y() As Integer _
) As Integer _
Implements IComparer(Of Integer()).Compare
If x Is y Then Return 0
If x is Nothing Then Return -1
If y is Nothing Then Return 1
Dim C As Integer = x.Length.CompareTo(y.Length)
If C <> 0 then Return C
Dim L As Integer = x.Length
Dim M(0 To L-1) As Integer
Array.Copy(x, M, L)
Array.Sort(M)
Dim N(0 To L-1) As Integer
Array.Copy(y, N, L)
Array.Sort(N)
For I = 0 to L - 1
C = M(I).CompareTo(N(I))
If C <> 0 Then Return C
Next
Return 0
End Function
End Class
Best regards,
Branco.
Another possible solution is to generate *only* the unique partitions
for a given number of terms, which would relieve you from having to
sort the partitions or to have a specific comparer. Code follows. The
method Partition2.GetPartitions(Value, Count) returns a List(Of Integer
()) with all the unique partitions with the specified count of terms.
Sub Main()
Console.Write("Value: ")
Dim L As Integer = Convert.ToInt32(Console.ReadLine)
Do While L > 0
For Each I As Integer() _
In Partition2.GetPartitions(L, 4)
For Each J As Integer In I
Console.Write("{0} ", J)
Next
Console.WriteLine
Next
Console.WriteLine
Console.Write("Value: ")
L = Convert.ToInt32(Console.ReadLine)
Loop
End Sub
Public Class Partition2
Private mList As List(Of Integer())
Public Function Partition( _
Value As Integer, _
Count As Integer _
) As List(Of Integer())
Dim P(0 To Count-1) As Integer
Dim R As New List(Of Integer())
mList = R
DoPartition(P, Value, Value, 0, Count)
mList = Nothing
Return R
End Function
Private Sub DoPartition( _
P() As Integer, _
Limit As Integer, _
Value As Integer, _
Pos As Integer, _
Max As Integer _
)
If Max = 0 Then
If Value = 0 Then
Dim R(0 To P.Length - 1) As Integer
Array.Copy(P, R, P.Length)
mList.Add(R)
End If
Return
End If
Dim First As Integer = Value - Max + 1
For I As Integer = First To 1 Step - 1
If I <= Limit Then
Dim N As Integer = Value - I
P(Pos) = I
DoPartition(P, I, N, Pos + 1, Max - 1)
End If
Next
End Sub
Shared Function GetPartitions( _
Value As Integer, _
Count As Integer _
) As List(Of Integer())
Return New Partition2().Partition(Value, Count)
End Function
End Class
Enregistrer un commentaire