Member Avatar for Gotcha

If someone could help me doing a code in VB to do the following:

The output should be a list of all posible ways in which (m) different Males
and (f) different female could be line up if no two females could be together
(one female can not stand after another female in the line).

Thanks for any suggestions,

EMG

  • 4 Contributors
  • 4 Replies
  • 241 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by jwenting

Dani AI

Generated

As asked: list every ordering of m distinct males and f distinct females so that no two females are adjacent. 's hint about a recurrence is useful for counting, but producing the actual list is easiest with a constructive approach: arrange the m males (m! ways), there are m+1 “slots” (before, between, after males) and choose f of those slots (C(m+1, f)), then permute the f females (f! ways). Valid arrangements exist only when f <= m+1. The total count is

m! C(m+1, f) f! (zero if f > m+1).

The code below implements that construction in VB.NET: generate all male permutations, generate all combinations of slots, then assign each permutation of females into the chosen slots and output the interleaved line. It also shows a BigInteger-based count so large values won't overflow.

Imports System
Imports System.Collections.Generic
Imports System.Numerics

Module NonAdjacentFemales
  ' Permutations, combinations, counting and listing
  Function Permutations(Of T)(items As IList(Of T)) As List(Of List(Of T))
    Dim result As New List(Of List(Of T))()
    If items.Count = 0 Then
      result.Add(New List(Of T)())
      Return result
    End If
    For i As Integer = 0 To items.Count - 1
      Dim e = items(i)
      Dim rest As New List(Of T)(items)
      rest.RemoveAt(i)
      For Each p In Permutations(rest)
        Dim np As New List(Of T)(p)
        np.Insert(0, e)
        result.Add(np)
      Next
    Next
    Return result
  End Function

  Sub GetCombinationsRecursive(n As Integer, k As Integer, start As Integer, current As List(Of Integer), res As List(Of List(Of Integer)))
    If k = 0 Then
      res.Add(New List(Of Integer)(current))
      Return
    End If
    For i As Integer = start To n - k
      current.Add(i)
      GetCombinationsRecursive(n, k - 1, i + 1, current, res)
      current.RemoveAt(current.Count - 1)
    Next
  End Sub

  Function GetCombinations(n As Integer, k As Integer) As List(Of List(Of Integer))
    Dim r As New List(Of List(Of Integer))()
    If k < 0 OrElse k > n Then Return r
    GetCombinationsRecursive(n, k, 0, New List(Of Integer)(), r)
    Return r
  End Function

  Function FactorialBig(n As Integer) As BigInteger
    Dim r As BigInteger = 1
    For i As Integer = 2 To n
      r *= i
    Next
    Return r
  End Function

  Function CombinationBig(n As Integer, k As Integer) As BigInteger
    If k < 0 OrElse k > n Then Return 0
    Return FactorialBig(n) / (FactorialBig(k) * FactorialBig(n - k))
  End Function

  Sub ListArrangements(males As List(Of String), females As List(Of String))
    Dim m = males.Count, f = females.Count
    If f > m + 1 Then
      Console.WriteLine("No valid arrangements (f > m + 1).")
      Return
    End If
    Console.WriteLine("Total count: " & (FactorialBig(m) * CombinationBig(m + 1, f) * FactorialBig(f)).ToString())
    For Each pm In Permutations(males)
      For Each combo In GetCombinations(m + 1, f)
        For Each pf In Permutations(females)
          Dim line As New List(Of String)()
          Dim femaleAt As New Dictionary(Of Integer, String)()
          For j As Integer = 0 To combo.Count - 1
            femaleAt(combo(j)) = pf(j)
          Next
          For slot As Integer = 0 To m
            If femaleAt.ContainsKey(slot) Then line.Add(femaleAt(slot))
            If slot < m Then line.Add(pm(slot))
          Next
          Console.WriteLine(String.Join(" ", line))
        Next
      Next
    Next
  End Sub
End Module

Notes and pitfalls: the output size grows factorially — for modest m+f the list can become enormous (stream results to a file rather than keeping them in memory). For counting only, use the formula above (recurrence approaches from give the same count). If some persons are identical, divide by duplicate factorials. As offered to code it, the snippet here is a complete, practical implementation; 's sarcasm is understandable given how quickly results blow up for even small inputs.

Recommended Answers

All 4 Replies

Member Avatar for Rashakil Fol

Use a recurrent relation. Or don't.

Member Avatar for server_crash

If someone could help me doing a code in VB to do the following:

The output should be a list of all posible ways in which (m) different Males
and (f) different female could be line up if no two females could be together
(one female can not stand after another female in the line).

Thanks for any suggestions,

EMG

Would you like me to write the whole thing for you?

Member Avatar for Gotcha

Would you like me to write the whole thing for you?

It would be fine.

Member Avatar for jwenting

It would be fine.

That was sarcasm :cheesy:

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.