locked
Combination without repitition RRS feed

  • Question

  • Hi guys

    I am hoping someone can help me with this PowerShell script.

    The script lists the unique combination of 26 letter alphabet ($List) based on 3 letter ($k)

    If I keep the $List shorter like A to K for instance, it works. But with 26 letter it doesn't work

    Thank you

    #########

    $List = "A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"
    $k = 3

    Add-Type @"
    public class Shift {
         public static int   Right(int x,   int count) { return x >> count; }
         public static uint  Right(uint x,  int count) { return x >> count; }
         public static long  Right(long x,  int count) { return x >> count; }
         public static ulong Right(ulong x, int count) { return x >> count; }
         public static int    Left(int x,   int count) { return x << count; }
         public static uint   Left(uint x,  int count) { return x << count; }
         public static long   Left(long x,  int count) { return x << count; }
         public static ulong  Left(ulong x, int count) { return x << count; }
      }                   
    "@

    function CombinationWithoutRepetition ([int]$k, $List)
    {
      Function IsNBits ([long]$value, $k, $length)
      {
        $count = 0
        for ($i = 0 ; $i -le $length ; $i++)
        {
          if ($value -band 1)
          {
            $count++
          }
          $value = [shift]::Right($value,1)
        }

        if ($count -eq $k)
        {
          return $true
        }
        else
        {
          return $false
        }
      }

      Function BitsToArray ([long]$value, $List)
      {
        $res = @()
        for ($i = 0 ; $i -le $List.length ; $i++)
        {
          if ($value -band 1)
          {
            $res += $List[$i]
          }
          $value = [shift]::Right($value,1)
        } 

        return ,$res
      }

      [long]$i = [Math]::Pow(2, $List.Length)
      $res = @()
      for ([long]$value=0 ; $value -le $i ; $value++)
      {
        if ((IsNBits $value $k $List.Length) -eq $true)
        {
          #write-host $value
          $res += ,(BitsToArray $value $List)
        }
      }
      return ,$res
    }

    Clear-Host
    $res = CombinationWithoutRepetition $k $List
    $res.count
    $res | Sort-Object | % { $_ -join ','}

    • Moved by Bill_Stewart Friday, January 26, 2018 3:23 PM This is not "do my homework for me" forumn
    Saturday, December 9, 2017 9:44 PM

All replies

  • You fail to say what you are trying to accomplish.  The code you posted does not work at all.  It won't compile.

    \_(ツ)_/

    Saturday, December 9, 2017 9:50 PM
  • This generates all combinations of a set selected by 'N'.

    Function Get-Combinations {
      <#
        .Synopsis
          Generates combinations from an array of multi-dimensional arrays
        .Description
          Get-Combinations is a recursive function designed to return combination sets from defined arrays. All arrays are passed as a single parameter.
        .Parameter Object
          The multi-dimensional input array. All elements within the array are cast to System.String.
        .Parameter Seperator
          Joins each element using the specified character.
        .Parameter CurIndex
          The current outer-array index, used in recursion.
        .Parameter Return
          A composite return value, used in recursion.
        .Example
          Get-Combinations @($Array1, $Array2, $Array3)
        .Example
          Get-Combinations @("site", @("web", "app"), @("01", "02"))
      #>
          
      Param(
       [Object[]]$Object,
       [String]$Seperator,
       [UInt32]$CurIndex = 0,
       [String]$Return = ""
      )
    
      $MaxIndex = $Object.Count - 1
      $Object[$CurIndex] | ForEach-Object {
        [Array]$NewReturn = "$($Return)$($Seperator)$($_)".Trim($Seperator)
        If ($CurIndex -lt $MaxIndex) {
          $NewReturn = Get-Combinations $Object -CurIndex ($CurIndex + 1) -Return $NewReturn
        }
        $NewReturn
      }
    }
    
    $CharacterSet = ([Int][Char]"A")..([Int][Char]"Z") | ForEach-Object { [Char]$_ }
    
    Get-Combinations @($CharacterSet, $CharacterSet, $CharacterSet)
    
    
    https://www.experts-exchange.com/questions/28078528/Calculate-all-possible-permutations-of-characters-in-a-set.html


    \_(ツ)_/

    Saturday, December 9, 2017 10:06 PM
  • Thanks for the reply :)

    Your code result with repetition of letters, like AAA

    I would like to have no repetition of any letter, like ABC, ABD etc

    If you shorten $List on my screen like ($List = "A","B","C","D","E","F","G","H","I","J","K") it works

    best regards

    Saturday, December 9, 2017 10:21 PM
  • Use the code I posted and filter out all combinations with duplicate letters.  This is the fastest way.

    In any case your code should be a recursive function.  The concept of "groups of N" is a recursive concept.

    You can also edit the function to test each group for duplicate characters and discard it.


    \_(ツ)_/

    Saturday, December 9, 2017 10:27 PM
  • Thanks jrv

    Sorry my powershell skills are not that good. I have taken that script from internet. 

    Can you give me example of how I can filter out duplicate letters?

    Or edit the function to test each group for duplicates?

    thank you

    Saturday, December 9, 2017 10:35 PM
  • I this a homework question?

    Hint:

    PS D:\scripts> (('ABC').ToCharArray()|Group).Count -lt 3
    False
    PS D:\scripts> (('ABA').ToCharArray()|Group).Count -lt 3
    True
    PS D:\scripts>


    \_(ツ)_/

    Saturday, December 9, 2017 10:38 PM
  • No, it's not :)

    Thank you jvc

    I will try that. Hope I can work that out :)

    best regards

    Saturday, December 9, 2017 10:54 PM
  • Here is an easier uniqueness rule:

    (($_).ToCharArray() | Sort-Object -unique).Count -eq 3


    \_(ツ)_/

    Saturday, December 9, 2017 10:58 PM
  • Hi jrv

    Sorry, I tried but couldn't work out how I use that last uniqueness rule. I said, I am not very good with powershell :)

    Can you please show me how/where I use it in your script?

    best regards

    Sunday, December 10, 2017 1:27 AM
  • Can you first explain the purpose of this exercise?


    \_(ツ)_/

    Sunday, December 10, 2017 1:32 AM
  • Sure jrv

    I want to list all unique values of list selected by N so I can do a pattern analysis of some old text

    In my case, position of letters doesn't matter. i.e ABC = BCA, so BCA shouldn't be listed.
    26 character letters combination by N=3 should list, (28*27*26/3*2*1)=3276 results.
    I should also be able to change N value

    Best regards

    Sunday, December 10, 2017 3:40 PM
  • That does not explain the purpose of this.  Why do you need to do this. 

    To get you results just add a filter for each rule.  You can alos crate a set of all ascii codes and define a formula that generates the pure combinations or permutations of N.


    \_(ツ)_/

    Sunday, December 10, 2017 6:54 PM
  • Hi jrv

    Sorry but I don't know how to do that.

    if you don't mind, can you please show me in the script?

    thank you

    Sunday, December 10, 2017 9:42 PM
  • Why do you need to do this?


    \_(ツ)_/

    Sunday, December 10, 2017 9:47 PM
  • I want to analyse text, to see if there is any pattern how the letters used. why is this important?

    I worked out your filter. If I do below, it sorts out the list but not exactly as I want it. I still get duplicates like ABC, BCA

    Get-Combinations@($CharacterSet,$CharacterSet,$CharacterSet) |Where-Object{(($_).ToCharArray() |Sort-Object-unique).Count -eq3}

    Can you show me how I can get all unique values?

    thank you

    Sunday, December 10, 2017 10:04 PM
  • To remove duplicates you need to sort each string and add it to a dictionary as the key.  Duplicates will be rejected.

    This seems to be a homework lesson as others have asked the almost identical question in other forums.

    If you just need the results then here is a full solution: https://planetcalc.com/4242/

    Enter your data and the results will be calculated.  There are links to the underlying code.


    \_(ツ)_/

    Sunday, December 10, 2017 10:09 PM
  • thanks jrv

    I have been searching the forums but couldn't find exactly what I was looking for.

    That link you provided will help me. Thank you very much.

    When I have time, I will have a go at creating powershell script myself for offline use :)

    best reagrds

    Sunday, December 10, 2017 10:48 PM