Asked  7 Months ago    Answers:  5   Viewed   30 times

For example I have this array:

int a[] = new int[]{3,4,6,2,1};

I need list of all permutations such that if one is like this, {3,2,1,4,6}, others must not be the same. I know that if the length of the array is n then there are n! possible combinations. How can this algorithm be written?

Update: thanks, but I need a pseudo code algorithm like:

for(int i=0;i<a.length;i++){
    // code here
}

Just algorithm. Yes, API functions are good, but it does not help me too much.

 Answers

66

If you're using C++, you can use std::next_permutation from the <algorithm> header file:

int a[] = {3,4,6,2,1};
int size = sizeof(a)/sizeof(a[0]);
std::sort(a, a+size);
do {
  // print a's elements
} while(std::next_permutation(a, a+size));
Tuesday, June 1, 2021
 
commonpike
answered 7 Months ago
85

If we had three groups of ten items, we could use a counter that goes from 0 to 999, and split the number into digits.

For example,

456 
   % 10 = 6  --------------------------  Item 6 (7th item) in the first group
   / 10 = 45
             % 10 = 5  ----------------  Item 5 (6th item) in the second group
             / 10 = 4
                       % 10 = 4  ------  Item 4 (5th item) in the third group
                       / 10 = 0

This algorithm converts a number into base 10. If we wanted to convert to octal, we would have used 8 instead of 10. 10 (or 8) is used throughout because each position has the same number of symbols, but this algorithm also works if the number of symbols varies from position to position.

2
   % 2 = 0  ------------------------  Item 0 (1st item) in the first group: Toppe
   / 2 = 1
     ^      % 2 = 1  ---------------  Item 1 (2nd item) in the second group: Small
     |      / 2 = 0
     |        ^      % 1 = 0  ------  Item 0 (1st item) in the third group: Rod
     |        |      / 1 = 0
     |        |        ^
     |        |        |
     |        |        +------------  Number of items in third group
     |        +---------------------  Number of items in second group
     +------------------------------  Number of items in first group

This gives us:

0 = ( 0 * 1 + 0 ) * 2 + 0 = Toppe, Extra_small, Rod
1 = ( 0 * 1 + 0 ) * 2 + 1 = Bukser_og_Jeans, Extra_small, Rod
2 = ( 0 * 1 + 1 ) * 2 + 0 = Toppe, Small, Rod
3 = ( 0 * 1 + 1 ) * 2 + 1 = Bukser_og_Jeans, Small, Rod

The following is a Perl implementation:

my %refinements = (
   Type => [
      'Toppe',
      'Bukser_og_Jeans',
   ],
   Size => [
      'Extra_small',
      'Small',
   ],
   Colour => [
      'Rod',
   ],
);

my @groups = values(%refinements);
my $iter = 0;
while (1) {
   my $num = $iter++;

   my @pick;
   for my $group (@groups) {
      my $r = $num % @$group;
      $num = ( $num - $r ) / @$group;
      push @pick, $group->[$r];
   }

   last if $num > 0;

   say join(', ', @pick);
}

I know it's not PHP—I don't know PHP—but you're just asking how to solve the problem, not necessarily the code to do it, right? It's my hope that you can understand the above Perl code enough to solve your problem and re-implement it in PHP.

(If I was actually writing a Perl solution, I'd use Algorith::Loops's NestedLoops.)

Wednesday, March 31, 2021
 
Muazam
answered 9 Months ago
27

There are several tools that works like JavaDoc for C++ The most popular tool is probably doxygen. It can handle JavaDoc-like comments, and also several languages (e.g., C++, C, Java, Objective-C, Python, PHP, C#). It has pretty good support for tweaking the style of the HTML output using CSS (see the users list for example documentations).

Two important issues when choosing the documentation system is to make sure that it allows you to

  • Document the entities that you are interested in. Do you want to document the system following the code structure or according to some other module division.
  • Getting the output formatted as you want. It is preferable when the documentation fits in with your general project style.

Our experience with doxygen is that it is pretty easy to set up and use, and the resulting output is fairly easy to tweak. Unfortunately, doxygen is not perfect, so in some cases it is necessary to work around quirks or bugs where the doxygen parser breaks down. Be sure to inspect all of your generated documentation carefully.

Sunday, August 8, 2021
 
ranhan
answered 4 Months ago
86

Take a look at the Modular Exponentiation algorithm.

The idea is not to compute 2^n. Instead, you reduce modulus d multiple times while you are powering up. That keeps the number small.

Combine the method with Exponentiation by Squaring, and you can compute (2^n)%d in only O(log(n)) steps.

Here's a small example: 2^130 % 123 = 40

2^1   % 123 = 2
2^2   % 123 = 2^2      % 123    = 4
2^4   % 123 = 4^2      % 123    = 16
2^8   % 123 = 16^2     % 123    = 10
2^16  % 123 = 10^2     % 123    = 100
2^32  % 123 = 100^2    % 123    = 37
2^65  % 123 = 37^2 * 2 % 123    = 32
2^130 % 123 = 32^2     % 123    = 40
Tuesday, September 28, 2021
 
DiglettPotato
answered 2 Months ago
16

To avoid problems of terminology: I wrote a small program:

  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

and that's its output:

  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

If that looks like a seed to a solution of your problem, just say so and I will post the code for the cOdoDemo class.

Code for 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/
'  !! http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-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

Some hints/remarks: Think of an odometer that genererates all combinations for 6 (7?) places/digits in numerical order. Now imagine an odometer that lets you specify a sequence/ordered set of 'digits'/words/items for each place/slot. This specification is done by aaItems.

This is the code for cPad, used in .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

Sorry for the missing documentation. I'll try to answer all your question.

Sunday, December 5, 2021
 
Ergwun
answered 1 Day ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share