Erzeugen Sie eine zufällige Störung

30

Herausforderungsbeschreibung

Eine "Störung" einer Sequenz ist eine Permutation, bei der kein Element an seiner ursprünglichen Position erscheint. Zum Beispiel ECABDist eine Störung von ABCDE, ist aber CBEDAnicht:

ABCDE
 | |   <- B and D are in their orignal positions
CBEDA

Erzeugen Sie bei gegebener Sequenz eine zufällige Störung.

Anmerkungen

  • Sie können entweder eine Zeichenfolge als Eingabe oder ein Array / eine Liste von Elementen (Ganzzahlen, Zeichen, Objekte ...) verwenden.

  • Anstatt ein neues Objekt zurückzugeben, können Sie ein vorhandenes ändern, indem Sie seine Elemente austauschen

  • Jede Störung sollte die gleiche Wahrscheinlichkeit haben, erzeugt zu werden

  • Sie können davon ausgehen, dass die Sequenz mehr als ein Element enthält und keines mehr als einmal vorkommt

shooqie
quelle
4
Verbunden?
Addison Crump
3
@VoteToClose: haha, total
kaputt
Ich weiß nicht viel darüber, aber hängt das in irgendeiner Weise mit dem Fixpunktsatz zusammen ... wonach die Dinge immer in ihrer eigenen Position enden werden oder so ähnlich ...? Ich wette, ich liege falsch, aber jemand korrigiert mich bitte :)
Farhan Anam
Gibt es eine Garantie dafür, dass die Elemente eindeutig sind, oder können sie Duplikate enthalten?
Carcigenicate
1
@Carcigenicate: Es ist genau dort in der Beschreibung; Sie können davon ausgehen, dass es keine Duplikate gibt
shooqie

Antworten:

12

CJam , 14 Bytes

q:X{mr_X.=:|}g

Probieren Sie es online!

Mische die Eingabe so lange, bis sie eine Störung darstellt.

Erläuterung

q:X   e# Read input and store it in X.
{     e# While the condition at the end of the loop is truthy...
  mr  e#   Shuffle the string.
  _X  e#   Duplicate it and push the input.
  .=  e#   Element-wise equality check.
  :|  e#   Reduce OR over the list, gives something truthy if any character
      e#   remained in its original position.
}g
Martin Ender
quelle
1
Ich wünschte, OP hätte spezifiziert, dass Lösungen garantieren müssten, dass sie immer fertig sind.
John Dvorak
4
@JanDvorak Nun, die Wahrscheinlichkeit, dass dies nicht gelingt, ist 0. Aber Sie haben Recht, dass eine deterministische Laufzeit die Herausforderung interessanter gemacht hätte.
Martin Ender
Ist die Wahrscheinlichkeit tatsächlich 0? Der Shuffle-Vorgang wird nicht perfekt sein, wie funktioniert das eigentlich? Ich denke, dies ist wahrscheinlich eine gute Annäherung an das, was das OP gefordert hat, aber ich bezweifle, dass die Wahrscheinlichkeiten für jede Störung gleich sind (wahrscheinlich hängt dies von einem Startwert des PRNG ab, der wahrscheinlich für die Mischoperation verwendet wird).
Niemand
3
@Nobody Ich bezweifle, dass Sie mit einem PRNG mit einem beliebigen Algorithmus perfekt einheitliche Ergebnisse erzielen können . Unter der Annahme, dass das Shuffle selbst einheitlich ist (was in der Java-Dokumentation mit "Alle Permutationen treten mit ungefähr gleicher Wahrscheinlichkeit auf" angegeben ist), führt eine Lösung auf Ablehnungsbasis auch zu einheitlichen Abweichungen, da jede Abweichung eine und jede Abweichung ist Permutation hat die gleiche Wahrscheinlichkeit.
Martin Ender
1
@ Nobody Math Nerd hier. Eine Bedingung, die entweder erfolgreich ist oder fehlschlägt, wird in der Statistik als Bernoulli-Studie bezeichnet. Dies impliziert, dass die Wahrscheinlichkeit, dass k Versuche zum ersten Erfolg benötigt werden, (1 - p) ^ (k - 1) * p ist, wobei p die Wahrscheinlichkeit einer erfolgreichen Störung ist. Es ist leicht zu erkennen, dass mit zunehmender Größe von k die Wahrscheinlichkeit, dass k Versuche erforderlich sind, verschwindend gering wird. Daher sagen wir, dass der Algorithmus mit Wahrscheinlichkeit 1 anhält ("fast sicher"), aber es ist nicht unmöglich, dass er niemals anhält.
Diener
9

Gelee , 6 Bytes

Ẋ=³S$¿

Probieren Sie es online!

Erläuterung

Ẋ    ¿    Shuffle the given list while this is nonzero for it:
    $       A two-step process:
 =³           Element-wise equality of it and L (the original list)...
   S          Sum the ones in this binary array.

Jonathan Allan hat ein Byte gespeichert.

Lynn
quelle
5
Hast du deinen Winter Bash Hut also rechtzeitig? :-)
Luis Mendo
2
Zeit, um ein schönes neues Bild zu zeichnen, Ẋ=³S$¿speichert ein Byte.
Jonathan Allan
2
Huh, das habe ich nie gewusst $. Vielen Dank!
Lynn
Es sind 6 Zeichen, aber mehr als 6 Bytes. Ẋ = ³S $ ¿Bytelängen sind: 312112. Insgesamt also 10 Bytes.
16.
6

Python, 85 Bytes

Ändert die übergebene Liste (von Meta und in der Frage zugelassen).

from random import*
def D(l):
 o=l[:]
 while any(x==y for x,y in zip(o,l)):shuffle(l)

Probieren Sie es hier online aus!

FlipTack
quelle
1
Wenn Sie Python angeben 2, ich glaube , Sie ersetzen könnte def D(l):mit l=input()und dann die Vertiefung Räume in den folgenden Zeilen speichern (so Sie ein Programm statt eine Funktion haben). Hat aber nicht abgelehnt!
Mathmandan
@mathmandan gute Idee, aber dann müsste ich es wieder ausdrucken, wenn es ein volles Programm ist, das mehr Bytes kostet.
FlipTack
1
Ok, wenn du meinst. Ich denke, die Spezifikation schien zu sagen, dass Sie das Ergebnis nicht ausdrucken oder zurückgeben mussten - es würde ausreichen, eine Liste [von der Benutzereingabe] zu nehmen und sie zu mischen. Es ist jedoch sinnvoll, "Vorhanden" als "Vorhanden vor dem Ausführen eines Codes" zu lesen. In diesem Fall stimme ich Ihnen zu. (Vielleicht gibt es einen gut etablierten Konsens darüber.) :)
Mathmandan
5

ES6 (Javascript), 7169 Bytes

Eingabe und Ausgabe sind Arrays und sollten mit allen Elementtypen (Zeichenfolgen, Zahlen usw.) funktionieren, sofern sie mit "==" verglichen werden können.

Golf gespielt

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

Prüfung

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

F(['A','B','C','D'])
Array [ "D", "C", "A", "B" ]

F(['A','B','C','D'])
Array [ "D", "A", "B", "C" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

F(['A','B','C','D'])
Array [ "D", "C", "B", "A" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

Interaktives Snippet

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

function G() {
    console.log(F(T.value.split``).join``); 
}
<input id=T value="ABCDEF"><button id=G onclick="G()">GENERATE</button>

Zeppelin
quelle
5

Perl 6 , 33 Bytes

{first (*Zne$_).all,.pick(*)xx *}

Ein Lambda, das eine Liste von ganzen Zahlen oder Zeichen als Eingabe verwendet und eine neue Liste zurückgibt.

Wenn es Listen von beliebigen Werten unterstützen muss, nemüsste durch !eqv(+2 Bytes) ersetzt werden.

( Probieren Sie es online. )

Erläuterung:

  • { }: Definiert ein Lambda.
  • .pick(*): Erzeugt eine zufällige Mischung aus der Eingabeliste.
  • .pick(*) xx *: Erzeugt eine langsame unendliche Folge solcher Mischvorgänge.
  • (* Zne $_).all: Ein Lambda, das zwei Listen (sein Argument *und das Argument des äußeren Lambdas $_) mit dem neOperator (negative Zeichenfolgengleichheit) komprimiert, was eine Liste von Booleschen Werten ergibt, und anschließend eine allJunction erstellt, um sie in einen einzelnen Booleschen Zustand zu reduzieren .
  • first PREDICATE, SEQUENCE: Nimmt das erste Element aus unserer unendlichen Folge von Permutationen, das den "Derangement" -Test erfüllt.
smls
quelle
4

Brachylog , 19 18 15 13 Bytes

@~.:?z:#da;?&

Probieren Sie es online!

Erläuterung

@~.                Output is a shuffle of the input
  .:?z             Zip the output with the input
      :#da         All couples of integers of the zip must be different
          ;      Or
           ?&      Call recursively this predicate with the same input
Tödlich
quelle
3

Perl 6 , 45 Bytes

{(@^a,{[.pick(*)]}...{none @a Zeqv@$_})[*-1]}
{(@^a,{[.pick(*)]}...{!sum @a Zeqv@$_})[*-1]}

Versuch es

Input ist ein Array von allem.

Erweitert:

{
  (

    @^a,          # declare parameter, and seed sequence generator

    {             # lambda with implicit parameter 「$_」
      [           # store into an array
        .pick(*)  # shuffle 「$_」
      ]
    }

    ...           # keep generating the sequence until

    {
      none        # none
      @a          # of the outer blocks input
      Z[eqv]      # is zip equivalent
      @$_         # with the current value being tested
    }

  )[ * - 1 ]      # return the last value
}
Brad Gilbert b2gills
quelle
3

MATL, 7 Bytes

Dies ist eine Übersetzung meines Octave-Posts (und ähnlich wie bei einigen anderen Einsendungen hier). Ich habe gestern meinen ersten MATL-Beitrag gepostet (CNR-Riss). Ich denke, das ist nicht optimal, aber es ist das Beste, was ich bisher habe.

Um ehrlich zu sein, bin ich mir nicht ganz sicher, ob ich tdort gebraucht wird, aber es ist der einzige Weg, wie ich das zum Laufen bringen kann. Es wird verwendet, damit ich die Benutzereingaben (abgerufen mit G) mit der zufälligen Permutation vergleichen kann. Ich würde denken, ich könnte die beiden ohne vergleichen, aber ...?

Sowieso geht hier:

`Z@tG=a

`          % Loop
 Z@        % Random permutation of input
   t       % Duplicating the stack
    G      % Paste from clipboard G (user input)
     =     % Comparing the random permutation with the input (retrieved from clipboard)
      a    % any(input == random permutation)
           % Implicit end and display

Probieren Sie es online!

Stewie Griffin
quelle
Irgendwelche Verbesserungen? Brauche ich dort wirklich toder kann ich es loswerden? Es hat Spaß gemacht, in MATL Golf zu spielen ... :)
Stewie Griffin
:-) Ich verstehe nicht, wie ich das loswerden kann t(oder gleichwertig mit einem anderen G). Sie müssen für die nächste Iteration oder als Endergebnis etwas auf dem Stapel
belassen
3

Eigentlich 13 Bytes

;;WX╚│♀=ΣWX)X

Probieren Sie es online!

Erläuterung:

;;WX╚│♀=ΣWX)X
;;             make two copies of input
  WX╚│♀=ΣW     while top of stack is truthy:
   X             discard top of stack
    ╚            shuffle array
     │           duplicate entire stack
      ♀=         compare corresponding elements in shuffled and original for equality
        Σ        sum (truthy if any elements are in the same position, else falsey)
          X)X  discard everything but the derangement
Mego
quelle
2

Oktave, 56 55 Bytes

x=input('');while any(x==(y=x(randperm(nnz(x)))));end,y

Wir müssen verwenden, input('')da dies keine Funktion ist. Da ich die Eingabe auch als Zeichenfolge festlegen kann, können wir den dazugehörigen Trick verwenden nnz(x)==numel(x).

Erläuterung:

x=input('')            % Self-explanatory
while any(x==y)        % Loop until x==y has only 0s (i.e. no elements are equal)
y=x(randperm(nnz(x)))  % Continue to shuffle the indices and assign x(indices) to y
end                    % End loop
y                      % Display y

Vielen Dank an Luis, dass er bemerkt hat, dass die Eingabe eine Zeichenfolge sein kann. Daher könnte ich nnzanstelle der numelSpeicherung von zwei Bytes verwenden.

Stewie Griffin
quelle
Notiz an mich selbst: Lies das nächste Mal die ganze Frage :) Danke!
Stewie Griffin
1
Das passiert mir die ganze Zeit :-)
Luis Mendo
2

MATL, 13 Bytes

Dies ist eine gemeinsame Anstrengung von @LuisMendo und mir. Im Gegensatz zu vielen anderen Antworten ist diese hier deterministisch in dem Sinne, dass sie keine zufälligen Permutationen abtastet, bis sie eine Störung erhalten, sondern alle Störungen erzeugt und eine zufällig auswählt.

Y@tG-!Af1ZrY)

Probieren Sie es online!

Erläuterung

Y@tG-!Af1ZrY)
Y@             generate all permutatoins
  t            create a duplicate
   G-!A        find the (logical) indices of all valid derangements (where no character of the string is in the same position as the original string)
       f       convert logical to linear indices
        1Zr    choose one of those indices randomly
           Y)  get the derangement (from the ones we generated earlier) at this index
Fehler
quelle
2

Pyth - 10 9 Bytes

Dadurch wird die Eingabe weiter gemischt, während alle Zeichen den Zeichen an ihrem Index in der Eingabe entsprechen.

.WsqVHQ.S

Probieren Sie es hier online aus .

.W           Iterate while
 s           Sum, this is works as any() on a boolean list
  qV         Vectorized equality
   H         The lambda variable for the check step
   Q         The input
 .S          Shuffle
  (Z)        Lambda variable, implicit
 (Q)         Start .W with input, implicit
Maltysen
quelle
Können Sie bitte eine Erklärung hinzufügen. Ich wollte eine Pyth-Antwort schreiben. Ich weiß nicht viel darüber.
Gurupad Mamadapur
@ GurupadMamadapur sicher, würde mich auch freuen.
Maltysen
1
@GurupadMamadapur hinzugefügt. Wir haben ein Tutorial . Es ist ziemlich veraltet, bringt Ihnen aber die Grundlagen bei. Wenn Sie Hilfe in Bezug auf Pyth benötigen, können Sie mich gerne im Chat anpingen.
Maltysen
2

Mathematica, 57 Bytes

#/.x_:>RandomChoice@Select[Permutations@x,FreeQ[#-x,0]&]&

Unbenannte Funktion, die eine Liste von Whatevern als Eingabe und Ausgabe einer Liste verwendet. Nachdem alle Permutationen #der Eingabe generiert wurden x, behalten wir nur die bei, für die die Menge #-xder elementweisen Unterschiede kein a enthält 0. dann treffen wir eine (gleichmäßig) zufällige Auswahl aus dieser Menge.

Greg Martin
quelle
1
nett! Etwas länger #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&offensichtlich schneller im Training für lange Streicher
Martin
Warten Sie, Sie sagen mir, dass es in Mathematica keine eingebauten Funktionen für Störungen gibt? : o
shooqie
Ich hatte die Hälfte selbst ein eingebautes erwartet :)
Greg Martin
0

PHP, 85 Bytes

for($a=$b=str_split($argv[1]);array_diff_assoc($a,$b)!=$a;)shuffle($b);echo join($b);

Kopiert das Zeichenfolgenargument in zwei Arrays und mischt eines davon, bis der Unterschied zwischen ihnen (der auch die Indizes der Elemente vergleicht) gleich dem anderen ist. Laufen Sie mit -r.

Titus
quelle
0

R, 59 Bytes

z=x=1:length(y<-scan(,""));while(any(x==z))z=sample(x);y[z]

Liest eine Liste von Elementen nach STDIN, nimmt die Länge der Liste und beginnt mit dem Abtasten von Bereichen von 1 bis zur Länge, bis eine gefunden wird, die keine Stellen mit der geordneten Liste teilt. Dann druckt diese Liste.

JAD
quelle
0

Wunder , 32 Bytes

f\@[/>#I zip#=[#0a\shuf#0]?f a?a

Verwendung:

f\@[/>#I zip#=[#0a\shuf#0]?f a?a];f[1 2 3 4 5]

Erläuterung

Besser lesbar:

f\@[
  some #I zip #= [#0; a\ shuf #0]
    ? f a
    ? a
]

Rekursive Funktion f. Führt einen elementweisen Vergleich zwischen fder Eingabeliste von und einer gemischten Version der Eingabeliste durch. Wenn der Vergleich gleiche Werte ergibt, fwird er in der gemischten Liste aufgerufen. Andernfalls geben wir einfach die gemischte Liste zurück.

Mama Fun Roll
quelle
0

Ruby, 67 Bytes

def f a
while (a.zip(o=a.shuffle).map{|x,y|x-y}.index 0);end
o
end
DepressedDaniel
quelle
0

Oktave, 54 53 Bytes

@(a)((p=perms(a))(L=!any(p==a,2),:))(randi(sum(L)),:)

Generieren Sie alle Permutationen aund wählen Sie zufällig eine Zeile aus, die kein gemeinsames Element mit hat a.

Hinweis: Es ist aus Versehen das Gleiche wie @flawr MATL Antwort!

rahnema1
quelle
0

Clojure, 94 90 79 Bytes

#(let[s(shuffle %)](if(not(some(fn[[x y]](= x y))(map vector % s)))s(recur %)))

-4 Bytes durch Ändern der Bedingung innerhalb der Reduktion auf andund Inlining done?.

-11 Bytes durch Konvertieren der Reduktion in some.

WOOT! Schlage PHP.

Brute-Force-Methode. Mischt die Liste, solange sie ungültig ist. Das wird schnell dumm, wenn man bedenkt, dass es sich um eine Brute-Force-Methode handelt, die Doppelversuche nicht verhindert. In weniger als einer Sekunde wurden 1000 Dearangments einer 1000 Elemente langen Liste gefunden.

Ungolfed:

(defn dearang [ls]
  (let [s (shuffle ls)
        bad? (some (fn [[x y]] (= x y))
                (map vector ls s))]
    (if (not bad?) s (recur ls))))
Karzigenat
quelle
0

Clojure, 56 Bytes

#(let[s(shuffle %)](if((set(map = % s))true)(recur %)s))

Beachten Sie, dass eine Zeichenfolge nicht gemischt werden kann, durch seqoder übergeben werden muss vec.

Ursprünglich habe ich versucht, #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))aber recurAnsatz ist in der Tat kürzer als iterate.

Die Magie ist, dass (set(map = % s))entweder eine Menge von falsch, eine Menge von wahr oder eine Menge von wahr und falsch zurückgegeben wird. Dies kann als eine Funktion verwendet werden, wenn es enthält, truedann ist die Antwort true, sonst falsch nil. =ist glücklich, zwei Eingabeargumente zu nehmen, keine Notwendigkeit, es mit etwas zu umbrechen.

((set [false]) true)
nil

Vielleicht gibt es noch einen kürzeren Weg, um zu überprüfen, ob einer der Werte wahr ist?

NikoNyrh
quelle
0

APL, 11 Bytes.

Mit der Zeichenfolge im richtigen Argument:

⍵[⍋(⍴⍵)?⍴⍵]

Erläuterung

ρ⍵ Ruft die Länge (oder Form) des richtigen Arguments ab.

?gibt ein zufälliges Array (⍴⍵)dieser Zahlen zurück.

Gibt die Reihenfolge zurück, um sicherzustellen, dass keine Duplikate vorhanden sind.

⍵[..] Stellt die zufällige Auswahl der Zeichenfolge dar, die diesen Index verwendet.

Jacob Utley
quelle
Willkommen bei PPCG! Wir setzen voraus, dass alle Einträge gültige Funktionen oder vollständige Programme sind. Daher muss Ihre Antwort über ein Funktionsargument oder eine Eingabemethode eingegeben werden.
ETHproductions
Ich denke, es sollte jetzt den Anforderungen entsprechen. Es braucht das richtige Argument, oder .
Jacob Utley