Перестановка зубчатого массива

Question

Я пытаюсь создать перестановку многомерного массива в классическом asp (vbscript), и я серьезно застрял. Я пробовал несколько своих собственных функций, а также пытался скопировать несколько версий php, но я часто получаю что-то, что либо переходит в переполнение буфера / бесконечную рекурсию, либо я получаю результаты, которые больше похожи на комбинацию, чем на перестановку, если Я правильно понимаю различия.

Допустим, это для рубашки. Рубашка может иметь цвета, размеры и стили. (Действительная система допускает любое количество «групп» параметров (например, цвет, размер и т. Д.), А также любое количество параметров в каждой группе (каждый конкретный размер, каждый конкретный цвет и т. Д.).

Например:

small   med         lg      xl
red     blue        green   white
pocket  no-pocket

Обратите внимание, что количество элементов в любом измерении массива заранее неизвестно; кроме того, не все вторые измерения будут иметь одинаковое количество элементов.

Мне нужно перебирать каждую возможную уникальную опцию, которая содержит опцию из каждой строки. В этом конкретном примере было бы 32 варианта (потому что мне нужно игнорировать результаты, которые имеют пустое значение для любого заданного параметра, поскольку asp на самом деле не обрабатывает неровный массив так, как я ожидал. Итак: маленький красный карман маленький красный без кармана маленький синий карман маленький синий без кармана и т.д.

Как только я закончу эту часть, мне нужно будет интегрировать ее с некоторыми идентификаторами из базы данных, но я вполне уверен, что смогу выполнить эту часть самостоятельно. Это рекурсивная функция, которая убивает меня.

Кто-нибудь может указать мне хорошее начало или помочь? Любая помощь приветствуется!

Answer 1

Чтобы избежать проблем с терминологией: я написал небольшую программу:

  Dim aaItems : aaItems = Array( _
      Array( "small", "med", "lg", "xl" ) _
    , Array( "red", "blue", "green", "white" ) _
    , Array( "pocket", "no-pocket" ) _
  )

  Dim oOdoDemo : Set oOdoDemo = New cOdoDemo.init( aaItems )
  oOdoDemo.run 33

и вот ее вывод:

  0: small red pocket
  1: small red no-pocket
  2: small blue pocket
  3: small blue no-pocket
  4: small green pocket
  5: small green no-pocket
  6: small white pocket
  7: small white no-pocket
  8: med red pocket
  9: med red no-pocket
 10: med blue pocket
 11: med blue no-pocket
 12: med green pocket
 13: med green no-pocket
 14: med white pocket
 15: med white no-pocket
 16: lg red pocket
 17: lg red no-pocket
 18: lg blue pocket
 19: lg blue no-pocket
 20: lg green pocket
 21: lg green no-pocket
 22: lg white pocket
 23: lg white no-pocket
 24: xl red pocket
 25: xl red no-pocket
 26: xl blue pocket
 27: xl blue no-pocket
 28: xl green pocket
 29: xl green no-pocket
 30: xl white pocket
 31: xl white no-pocket
 32: small red pocket

Если это похоже на начальное значение для решения вашей проблемы, просто скажите, и я опубликую код для класса cOdoDemo.

Код для cOdoDemo:

'' cOdoDemo - Q&D combinations generator (odometer approach)
'
' based on ideas from:
'  !! http://www.quickperm.org/index.php
'  !! http://www.ghettocode.net/perl/Buzzword_Generator
'  !! http://www.dreamincode.net/forums/topic/107837-vb6-combinatorics-lottery-problem/
'  !! /131970/algoritm-vozvrata-vseh-kombinatsii-k-elementov-iz-n
Class cOdoDemo

Private m_nPlaces    ' # of places/slots/digits/indices
Private m_nPlacesUB  ' UBound (for VBScript only)
Private m_aLasts     ' last index for each place => carry on
Private m_aDigits    ' the digits/indices to spin around

Private m_aaItems    ' init: AoA containing the elements to spin
Private m_aWords     ' one result: array of combined

Private m_nPos       ' current increment position

'' init( aaItems ) - use AoA of 'words' in positions to init the
''                   odometer
Public Function init( aaItems )
  Set init = Me
  m_aaItems   = aaItems
  m_nPlacesUB = UBound( m_aaItems )
  m_nPlaces   = m_nPlacesUB + 1
  ReDim m_aLasts(  m_nPlacesUB )
  ReDim m_aDigits( m_nPlacesUB )
  ReDim m_aWords(  m_nPlacesUB )
  Dim nRow
  For nRow = 0 To m_nPlacesUB
      Dim nCol
      For nCol = 0 To UBound( m_aaItems( nRow ) )
          m_aaItems( nRow )( nCol ) = m_aaItems( nRow )( nCol )
      Next
      m_aLasts( nRow ) = nCol - 1
  Next
  reset
End Function ' init

'' reset() - start afresh: all indices/digit set to 0 (=> first word), next
''           increment at utmost right
Public Sub reset()
  For m_nPos = 0 To m_nPlacesUB
      m_aDigits( m_nPos ) = 0
  Next
  m_nPos = m_nPlacesUB
End Sub ' reset

'' tick() - increment the current position and deal with carry
Public Sub tick()
  m_aDigits( m_nPos ) = m_aDigits( m_nPos ) + 1
  If m_aDigits( m_nPos ) > m_aLasts( m_nPos ) Then ' carry to left
     For m_nPos = m_nPos - 1 To 0 Step -1
         m_aDigits( m_nPos ) = m_aDigits( m_nPos ) + 1
         If m_aDigits( m_nPos ) <= m_aLasts( m_nPos ) Then ' carry done
            Exit For
         End If
     Next
     For m_nPos = m_nPos + 1 To m_nPlacesUB ' zero to right
         m_aDigits( m_nPos ) = 0
     Next
     m_nPos = m_nPlacesUB ' next increment at utmost right
  End If
End Sub ' tick

'' map() - build result array by getting the 'words' for the
''         indices in the current 'digits'
Private Sub map()
  Dim nIdx
  For nIdx = 0 To m_nPlacesUB
      m_aWords( nIdx ) = m_aaItems( nIdx )( m_aDigits( nIdx ) )
  Next
End Sub ' map

'' run( nMax ) - reset the odometer, tick/increment it nMax times and
''               display the mapped/translated result
Public Sub run( nMax )
  reset
  Dim oPad : Set oPad = New cPad.initWW( Len( CStr( nMax ) ) + 1, "L" )
  Dim nCnt
  For nCnt = 0 To nMax - 1
      map
      WScript.Echo oPad.pad( nCnt ) & ":", Join( m_aWords )
      tick
  Next
End Sub ' run

End Class ' cOdoDemo

Некоторые подсказки / замечания: Подумайте об одометре, который генерирует все комбинации для 6 (7?) Мест / цифр в порядке номеров.Теперь представьте себе одометр, который позволяет вам указать последовательность / упорядоченный набор «цифр» / слов / предметов для каждого места / слота.Эта спецификация выполняется aaItems.

Это код для cPad, используемый в .run ():

''= cPad - Q&D padding
Class cPad
Private m_nW
Private m_sW
Private m_sS
Private m_nW1
Public Function initWW( nW, sW )
  m_nW       = nW
  m_nW1      = m_nW + 1
  m_sW       = UCase( sW )
  m_sS       = Space( nW )
  Set initWW = Me
End Function
Public Function initWWC( nW, sW, sC )
  Set initWWC = initWW( nW, sW )
  m_sS        = String( nW, sC )
End Function
Public Function pad( vX )
  Dim sX : sX = CStr( vX )
  Dim nL : nL = Len( sX )
  If nL > m_nW Then
     Err.Raise 4711, "cPad::pad()", "too long: " & nL & " > " & m_nW
  End If
  Select Case m_sW
    Case "L"
      pad = Right( m_sS & sX, m_nW )
    Case "R"
      pad = Left( sX & m_sS, m_nW )
    Case "C"
      pad = Mid( m_sS & sX & m_sS, m_nW1 - ((m_nW1 - nL) \ 2), m_nW )
    Case Else
      Err.Raise 4711, "cPad::pad() Unknown m_sW: '" & m_sW & "'"
  End Select
End Function
End Class ' cPad

Извините за отсутствующую документацию.Я постараюсь ответить на все ваши вопросы.

Answer 2

Универсальное решение в 20 строк!

Function Permute(parameters)

    Dim results, parameter, count, i, j, k, modulus

    count = 1
    For Each parameter In parameters
        count = count * (UBound(parameter) + 1)
    Next

    results = Array()
    Redim results(count - 1)

    For i = 0 To count - 1
        j = i
        For Each parameter In parameters
            modulus = UBound(parameter) + 1
            k = j Mod modulus
            If Len(results(i)) > 0 Then _
                results(i) = results(i) & vbTab
            results(i) = results(i) & parameter(k)
            j = j \ modulus
        Next
    Next

    Permute = results

End Function

Answer 3

Если вам нужно беспокоиться только об этих четырех фиксированных категориях, просто используйте вложенные циклы for.

Если число категорий может измениться, рекурсивное решение легко определить:

  permute(index, permutation[1..n], sources[1..n])
  1. if index > n then print(permutation)
  2. else then
  3     for i = 1 to sources[index].length do
  4.       permutation[index] = sources[index][i]
  5.       permute(index+1, permutation, sources)

Вызов с индексом = 0 и пустой перестановкой для достижения наилучших результатов (sources - это массив массивов, содержащих ваши категории).

Пример:

  index = 1
  sources = [[blue, red, green], [small, medium, large], [wool, cotton, NULL], [shirt, NULL, NULL]].
  permutation = [NULL, NULL, NULL, NULL]

  permute(index, permutation, sources)
   note: n = 4 because that's how many categories there are
   index > n is false, so...
   compute length of sources[1]:
    sources[1][1] isn't NULL, so...
    sources[1][2] isn't NULL, so...
    sources[1][3] isn't NULL, so...
    sources[1].length = 3

   let i = 1... then permutation[1] = sources[1][1] = blue
   permute(2, permutation, sources)

   etc.