Best shuffle: Difference between revisions

{{Template:Strings}}

<br><br>

=={{header|11l}}==

{{trans|Python}}

 

R sum(zip(w1, wnew).map((c1, c2) -> Int(c1 == c2)))

 

abba, baab ,(0)

</pre>

 

=={{header|Action!}}==

BYTE i,j,len

CHAR tmp

a, a, (1)

</pre>

=={{header|Ada}}==

{{trans|AWK}}

with Ada.Strings.Unbounded;

 

up, pu, ( 0 )

a, a, ( 1 )</pre>

=={{header|ALGOL 68}}==

{{Trans|Action!}}

PROC best shuffle = ( STRING orig )STRING:

BEGIN

a, a, (1)

</pre>

 

=={{header|Arturo}}==

 

count: function [s1 s2][

res: 0

a -> a | count: 1

antidisestablishmentarianism -> mesansrntbiissmtailihdaneait | count: 0</pre>

=={{header|AutoHotkey}}==

Loop Parse, Words,`,

out .= Score(A_LoopField, Shuffle(A_LoopField))

a, a, (1)

</pre>

=={{header|AWK}}==

{{trans|Icon}}

The Icon and Unicon program uses a simple algorithm of swapping. This is relatively easy to translate to Awk.

 

scram = best_shuffle($0)

print $0 " -> " scram " (" unchanged($0, scram) ")"

If those built-in array functions seem strange to you, and if you can understand these for loops, then you might prefer this Awk program. This algorithm counts the letters in the string, sorts the positions, and fills the positions in order.

 

# out["score"] = number of matching characters

function best_shuffle(out, s, c, i, j, k, klen, p, pos, set, rlen, slen) {

Output:

 

abracadabra, baarrcadaab, (0)

seesaw, essewa, (0)

The output might change if the <tt>for (c in set)</tt> loop iterates the array in a different order.

 

 

FOR z = 0 TO UBOUND(case$)-1

</pre>

 

{{works with|BBC BASIC for Windows}}

a$ = "seesaw" : b$ = FNshuffle(a$) : PRINT a$ " -> " b$ FNsame(a$,b$)

a$ = "elk" : b$ = FNshuffle(a$) : PRINT a$ " -> " b$ FNsame(a$,b$)

NEXT

= " (" + STR$(n%) + ")"</syntaxhighlight>

<pre>

abracadabra -> daaracababr (0)

a -> a (1)

</pre>

=={{header|Bracmat}}==

Not optimized:

( shuffle

= m car cdr todo a z count string

 

Optimized (~100 x faster):

( shuffle

= m car cdr todo a z count M string tried

{!} Done

</pre>

=={{header|C}}==

 

In essence: we form cyclic groups of character indices where each cyclic group is guaranteed to represent each character only once (two instances of the letter 'a' must have their indices in separate groups), and then we rotate each of the cyclic groups. We then use the before/after version of these cycles to shuffle the original text. The only way a character can be repeated, here, is when a cyclic group contains only one character index, and this can only happen when more than half of the text uses that character. This is C99 code.

 

#include <stdio.h>

#include <string.h>

 

===Version with random result===

#include <stdlib.h>

#include <string.h>

do_string("");

return 0;

grrrrrr -> rrgrrrr, overlap 5

elk -> kel, overlap 0

 

===Deterministic method===

#include <string.h>

 

return 0;

}</syntaxhighlight>

=={{header|C sharp|C#}}==

For both solutions, a class is used to encapsulate the original string and to scrambling. A private function of the class does the actual sorting. An implicit conversion from string is also provided to allow for simple initialization, e.g.:

Which will immediately shuffle each word.

 

A sequential solution, which always produces the same output for the same input.

using System;

using System.Text;

 

And a randomized solution, which will produce a more or less different result on every run:

using System;

using System.Text;

a, a, (1)

</pre>

=={{header|C++}}==

{{works with|C++|11}}

{{trans|Java}}

#include <sstream>

#include <algorithm>

a

a (1)</pre>

=={{header|Clojure}}==

Uses same method as J

 

(->> (map = before after)

(filter true? ,)

["up" "pu" 0]

["a" "a" 1]]</syntaxhighlight>

=={{header|Common Lisp}}==

(loop for c1 across string1 and c2 across string2

count (char= c1 c2)))

 

===Version 2===

(let (tbl out (shortest (length str)) (s str))

 

 

The output is:

seesaw: (ewsase 0)

elk: (kel 0)

a: (a 1)

</syntaxhighlight>

=={{header|Crystal}}==

{{trans|Ruby}}

 

# Fill _pos_ with positions in the order

# that we want to fill them.

a, a, (1)

</pre>

=={{header|D}}==

===Version with random result===

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

std.traits, std.typecons;

 

 

===Deterministic approach===

 

extern(C) pure nothrow void* alloca(in size_t size);

{{libheader| System.Generics.Collections}}

{{Trans|C#}}

program Best_shuffle;

 

end.

</syntaxhighlight>

=={{header|Elena}}==

import extensions;

import extensions'text;

extension op

{

 

}

 

public program()

{

 

 

}</syntaxhighlight>

{{out}}

=={{header|Erlang}}==

Deterministic version.

-module( best_shuffle ).

 

"a" "a" 1

</pre>

 

=={{header|FreeBASIC}}==

{{trans|Liberty BASIC}}

Dim As String*11 lista(6) => {"abracadabra","seesaw","pop","grrrrrr","up","a"}

 

a ==> a (puntuación: 1)

</pre>

=={{header|FutureBasic}}==

include "Tlbx GameplayKit.incl"

include "NSLog.incl"

 

local fn ShuffleString( string as CFStringRef ) as CFStringRef

end fn = fn ArrayComponentsJoinedByString( shuffledArr, @"" )

 

 

local fn StringDifferences( string1 as CFStringRef, string2 as CFStringRef ) as NSInteger

end fn = unchangedPosition

 

 

for i = 0 to 3

next

 

=={{header|Go}}==

{{trans|Icon and Unicon}}

 

import (

a -> a (1)

</pre>

=={{header|Groovy}}==

def shuffled = (text as List)

for (sourceIndex in 0..<text.size()) {

a, a, (1)

</pre>

=={{header|Haskell}}==

 

We demonstrate several approaches here. In order to test the program we define a testing suite:

 

 

printTest prog = mapM_ test texts

The core of the algorithm is swapping procedure similar to those implemented in AWK and Icon examples. It could be done by a pure program with use of immutable vectors (though it is possible to use mutable vectors living in <tt>ST</tt> or <tt>IO</tt>, but it won't make the program more clear).

 

import qualified Data.Vector as V

import Data.List (delete, find)

The program works but shuffling is not good in case of a real text, which was just shifted. We can make it better using [[Perfect shuffle]] (faro shuffle) before the swapping procedure.

 

perfectShuffle [] = []

perfectShuffle lst | odd n = b : shuffle (zip bs a)

Additional import:

 

 

randomShuffle [] = return []

randomShuffle lst = do

Using streaming technique it is possible to shuffle the sequence on the fly, using relatively small moving window (say of length k) for shuffling procedure. In that case the program will consume constant memory amount O[k] and require O[n*k] operations.

 

import Conduit

import Control.Monad.Random (getRandomR)

Additional imports

 

import Data.ByteString.Char8 (ByteString, unpack, pack)

import Data.Conduit.ByteString.Builder (builderToByteString)

import System.IO (stdin, stdout)</syntaxhighlight>

 

shuffleBS :: Int -> ByteString -> IO ByteString

shuffleBS n s =

$ cat input.txt | ./shuffle

aeotdR s aoiCtrpmmgi crn theemaysg srioT the tseo.dih psae re isltn ountstoeo tosmaetia es nssimhn ad kaeeinrlataffauytse g oanbs ,e ol e sio ttngdasmw esphut ro ganeemas g alsi arlaeefn,ranifddoii a drnp det r toi ahowgnutan n rgneanppi raohi d oaop blrcst imeioaer ngohrla.eRotn Cst n dce aenletya th8r3 n2ssout1 3dasktaft,rrk9as,a ss iewarf6 d2l ogu asga te g un oa hn4d enaodho(ctt)n, eha laovnsotusw oeinyetsakvn eo ienlrav ygtnu aer. g</pre>

=={{header|Icon}} and {{header|Unicon}}==

The approach taken requires 2n memory and will run in O(n^2) time swapping once per final changed character. The algorithm is concise and conceptually simple avoiding the lists of indices, sorting, cycles, groups, and special cases requiring rotation needed by many of the other solutions. It proceeds through the entire string swapping characters ensuring that neither of the two characters are swapped with another instance of themselves in the ''original'' string.

 

Additionally, this can be trivially modified to randomize the shuffle by uncommenting the line

while scram := bestShuffle(line := read()) do

write(line," -> ",scram," (",unchanged(line,scram),")")

->

</pre>

=={{header|J}}==

 

Based on [http://rosettacode.org/mw/index.php?title=Best_shuffle&oldid=97419#J Dan Bron's approach]:

 

yy=. <@({~ ?~@#)@I.@= y

y C.~ (;yy) </.~ (i.#y) |~ >./#@> yy

Example:

 

abracadabra, bdacararaab (0)

seesaw, eawess (0)

up, pu (0)

a, a (1)</syntaxhighlight>

=={{header|Java}}==

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

 

public class BestShuffle {

up pu (0)

a a (1)</pre>

=={{header|JavaScript}}==

 

Based on the J implementation (and this would be a lot more concise if we used something like jQuery):

 

var r= [];

for (var j= 0; j<a.length; j++)

Example:

 

<script type="text/javascript">

/* ABOVE CODE GOES HERE */

up, pu, (0)

a, a, (1)</pre>

=={{header|jq}}==

{{works with|jq|1.5}}

The implementation in this section uses the deterministic "swap" algorithm found in other entries on this page.

 

 

def swap($i;$j):

 

'''Examples:'''

| bestShuffle</syntaxhighlight>

 

a, a, (1)

antidisestablishmentarianism, maaaadisesitblishmenttrninis, (0)</pre>

=={{header|Julia}}==

{{trans|Python}}

 

function bestshuffle(str::String)::Tuple{String,Int}

up: pu (0)

a: a (1)</pre>

=={{header|Kotlin}}==

{{trans|Java}}

 

object BestShuffle {

up pu (0)

a a (1)</pre>

=={{header|Liberty BASIC}}==

list$ = "abracadabra seesaw pop grrrrrr up a"

 

up pu 0

a a 1</pre>

=={{header|Lua}}==

 

local function shuffle(t)

up, pu, (0)

a, a, (1)</pre>

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Flatten[{data,First[SortBy[

List[#, StringLength[data]-HammingDistance[#,data]] & /@ StringJoin /@ Permutations[StringSplit[data, ""]], Last]]}]

up, pu,(0)

a, a,(1)</pre>

=={{header|Nim}}==

{{trans|Java}}

import sequtils

import strutils

a a 1

antidisestablishmentarianism mietnshieistrlaatbsdsnaiinma 0</pre>

=={{header|OCaml}}==

 

Deterministic

 

let len = String.length s in

let r = String.copy s in

'up', 'pu' -> 0

'a', 'a' -> 1</pre>

=={{header|Pascal}}==

{{works with|Free_Pascal}}

function BestShuffle(s: string): string;

up, pu, (0)

a, a, (1)</pre>

 

=={{header|Perl}}==

The Algorithm::Permute module does not ship with perl, but is freely available from CPAN.

 

use warnings;

use List::Util qw(shuffle);

use Algorithm::Permute;

# there will be a \x00 in the "^" of the two words.

# The tr operator is then used to count the "\x00"s.

next if $score >= $best_score;

($best_word, $best_score) = ($word, $score);

swaps which will improve the score.

 

use warnings;

use List::Util qw(shuffle);

 

my $word = join '', @t;

 

print "$original_word, $word, $score\n";

}

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"abracadabra"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"seesaw"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"elk"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"grrrrrr"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"up"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"a"</span><span style="color: #0000FF;">}</span>

a -> a (1)

</pre>

=={{header|PHP}}==

Translation of [[Best_shuffle#Icon_and_Unicon|Icon]] via [[Best_shuffle#AWK|AWK]]

echo bestShuffle($w) . '<br>';

 

up pu (0)

a a (1)</pre>

=={{header|Picat}}==

Using a CP (Constraint Programming) solver guarantees an optimal solution. This is deterministic since the solve heuristic ("split") always give the same first result.

 

 

go =>

===All optimal solutions===

Using a constraint solver makes it quite easy to generate all optimal solutions.

Words = ["abracadabra",

"seesaw",

num_solutions = 1

solutions = [aaaaaaa]</pre>

=={{header|PicoLisp}}==

(let Lst NIL

(for C (setq Str (chop Str))

: (bestShuffle "a")

a a (1)</pre>

=={{header|PL/I}}==

declare (s, saves) character (20) varying, c character (1);

declare t(length(s)) bit (1);

A 1

</pre>

=={{header|PowerShell}}==

{{works with|PowerShell|3}}

# (Split out into separate function so we can use it separately in our output)

function Get-BestScore ( [string]$String )

return $Shuffle

}</syntaxhighlight>

{

$Shuffle = Get-BestShuffle $String

up, pu, (0)

a, a, (1)</pre>

=={{header|Prolog}}==

Works with SWI-Prolog

 

best_shuffle :-

===Version with random result===

====solution====

:- system:set_prolog_flag(double_quotes,codes) .

 

*/

</pre>

=={{header|PureBasic}}==

This solution creates cycles of letters of letters that are then rotated to produce the final maximal shuffle. It includes an extra sort step that ensures the original string to be returned if it is repeatedly shuffled.

Char.s

List Position.i()

up, pu, (0)

a, a, (1)</pre>

=={{header|Python}}==

===Swap if it is locally better algorithm===

With added randomization of swaps!

 

def count(w1,wnew):

===Alternative algorithm #1===

 

 

def best_shuffle(s):

up, pu, (0)

a, a, (1)</pre>

=={{header|Racket}}==

#lang racket

 

a, a, (1)

</pre>

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Sidef}}

 

my @s = $orig.comb;

my @t = @s.pick(*);

 

}

}

}

 

}

 

{{out}}

seesaw, wssaee, (0)

elk, lke, (0)

grrrrrr, rrrgrrr, (5)

up, pu, (0)

 

=={{header|Rascal}}==

{{incomplete|Rascal|No output given.}}

 

public tuple[str, str, int] bestShuffle(str s){

return (0 | it + 1 | n <- index(characters), permutations[n] == characters[n]);

}</syntaxhighlight>

=={{header|REXX}}==

parse arg $ /*get some words from the command line.*/

if $='' then $= 'tree abracadabra seesaw elk grrrrrr up a' /*use the defaults?*/

original: a new: a score: 1

</pre>

=={{header|Ring}}==

# Project : Best shuffle

 

a -> a 1

</pre>

=={{header|Ruby}}==

{{works with|Ruby|1.9}}

{{trans|Raku}}

 

# Fill _pos_ with positions in the order

# that we want to fill them.

a, a, (1)

</pre>

=={{header|Run BASIC}}==

 

while word$(list$,ii + 1," ") <> ""

up pu 0

a a 1</pre>

=={{header|Rust}}==

{{libheader|rand}}

extern crate rand;

 

a, a, (1)

</pre>

=={{header|Scala}}==

There are two implementations. One is simple but exponential and very inefficient. The second one is quadratic. Both are pure functional. Given quadratic solution has a bigger constant than the one used in the Python implementation, but doesn't use mutable datastructures.

def coincidients(s1: Seq[Char], s2: Seq[Char]): Int = (s1, s2).zipped.count(p => (p._1 == p._2))

def freqMap(s1: List[Char]) = s1.groupBy(_.toChar).mapValues(_.size)

</syntaxhighlight>

The test code:

def main(args: Array[String]): Unit = {

println(bestShuffle("abracadabra"));

</pre>

The ScalaCheck code

object BestShuffleSpecification extends Properties("BestShuffle") {

 

}

</syntaxhighlight>

=={{header|Scheme}}==

(define count

(lambda (str1 str2)

a a (1)

</pre>

=={{header|Seed7}}==

 

const func string: bestShuffle (in string: stri) is func

a, a, (1)

</pre>

=={{header|Sidef}}==

{{trans|Go}}

 

var s = orig.chars

up pu: 0

a a: 1</pre>

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}</syntaxhighlight>

Demonstration:

puts [bestshuffle $sample]

}</syntaxhighlight>

a,a,(1)

</pre>

=={{header|Ursala}}==

An implementation based on the J solution looks like this.

#import nat

 

main = ~&LS <.~&l,@r :/` ,' ('--+ --')'+ ~&h+ %nP+ length@plrEF>^(~&,shuffle)* words</syntaxhighlight>

A solution based on exponential search would use this definition of <code>shuffle</code> (cf. Haskell and Tcl).

output:

<pre>abracadabra caarrbabaad (0)

up pu (0)

a a (1)</pre>

=={{header|VBA}}==

 

Option Explicit

 

qwerty ==> eytwrq (Score : 0)

tttt ==> tttt (Score : 4)</pre>

=={{header|VBScript}}==

{{trans|Java}}

'VBScript Implementation

 

up,pu,(0)

a,a,(1)</pre>

=={{header|Wren}}==

{{trans|Kotlin}}

 

class BestShuffle {

 

=={{header|XPL0}}==

string 0; \use zero-terminated string convention

 

a, a, (1)

</pre>

=={{header|zkl}}==

{{trans|D}}

{{trans|Common Lisp}}

s:=str.split("").shuffle(); // -->List

if(not s) return(str,str.len()); // can't shuffle "" or "a"

return(s.concat(), s.zipWith('==,str).sum(0));

}</syntaxhighlight>

foreach s in (ss){

ns,cnt:=bestShuffle(s);

--> (0)

</pre>

=={{header|ZX Spectrum Basic}}==

{{trans|AWK}}

20 READ w$

30 GO SUB 1000

up pu 0

a a 1</pre>

{{omit from|bc|No string operations.}}

{{omit from|dc|No string operations.}}