← Catalogo
SIGN
PyJS

Enumerating Oriented Gene Orderings

CombinatoricsGenome Rearrangements

Pagina originale su rosalind.info

Descrizione

Una permutazione con segno di lunghezza n è un ordinamento degli interi positivi {1, 2, ..., n} in cui a ciascun intero viene assegnato un segno positivo o negativo. Ad esempio, π = (5, -3, -2, 1, 4) è una permutazione con segno di lunghezza 5.

Given

Un intero positivo n ≤ 6.

Return

Il numero totale di permutazioni con segno di lunghezza n, seguito dall'elenco di tutte tali permutazioni (in qualsiasi ordine).

Sample Dataset

2

Sample Output

8
-1 -2
-1 2
1 -2
1 2
-2 -1
-2 1
2 -1
2 1

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

4

Output · run_log.txt

OK
384
1 2 3 4
1 2 3 -4
1 2 -3 4
1 2 -3 -4
1 -2 3 4
1 -2 3 -4
1 -2 -3 4
1 -2 -3 -4
-1 2 3 4
-1 2 3 -4
-1 2 -3 4
-1 2 -3 -4
-1 -2 3 4
-1 -2 3 -4
-1 -2 -3 4
-1 -2 -3 -4
1 2 4 3
1 2 4 -3
1 2 -4 3
1 2 -4 -3
1 -2 4 3
1 -2 4 -3
1 -2 -4 3
1 -2 -4 -3
-1 2 4 3
-1 2 4 -3
-1 2 -4 3
-1 2 -4 -3
-1 -2 4 3
-1 -2 4 -3
-1 -2 -4 3
-1 -2 -4 -3
1 3 2 4
1 3 2 -4
1 3 -2 4
1 3 -2 -4
1 -3 2 4
1 -3 2 -4
1 -3 -2 4
1 -3 -2 -4
-1 3 2 4
-1 3 2 -4
-1 3 -2 4
-1 3 -2 -4
-1 -3 2 4
-1 -3 2 -4
-1 -3 -2 4
-1 -3 -2 -4
1 3 4 2
1 3 4 -2
1 3 -4 2
1 3 -4 -2
1 -3 4 2
1 -3 4 -2
1 -3 -4 2
1 -3 -4 -2
-1 3 4 2
-1 3 4 -2
-1 3 -4 2
-1 3 -4 -2
-1 -3 4 2
-1 -3 4 -2
-1 -3 -4 2
-1 -3 -4 -2
1 4 2 3
1 4 2 -3
1 4 -2 3
1 4 -2 -3
1 -4 2 3
1 -4 2 -3
1 -4 -2 3
1 -4 -2 -3
-1 4 2 3
-1 4 2 -3
-1 4 -2 3
-1 4 -2 -3
-1 -4 2 3
-1 -4 2 -3
-1 -4 -2 3
-1 -4 -2 -3
1 4 3 2
1 4 3 -2
1 4 -3 2
1 4 -3 -2
1 -4 3 2
1 -4 3 -2
1 -4 -3 2
1 -4 -3 -2
-1 4 3 2
-1 4 3 -2
-1 4 -3 2
-1 4 -3 -2
-1 -4 3 2
-1 -4 3 -2
-1 -4 -3 2
-1 -4 -3 -2
2 1 3 4
2 1 3 -4
2 1 -3 4
2 1 -3 -4
2 -1 3 4
2 -1 3 -4
2 -1 -3 4
2 -1 -3 -4
-2 1 3 4
-2 1 3 -4
-2 1 -3 4
-2 1 -3 -4
-2 -1 3 4
-2 -1 3 -4
-2 -1 -3 4
-2 -1 -3 -4
2 1 4 3
2 1 4 -3
2 1 -4 3
2 1 -4 -3
2 -1 4 3
2 -1 4 -3
2 -1 -4 3
2 -1 -4 -3
-2 1 4 3
-2 1 4 -3
-2 1 -4 3
-2 1 -4 -3
-2 -1 4 3
-2 -1 4 -3
-2 -1 -4 3
-2 -1 -4 -3
2 3 1 4
2 3 1 -4
2 3 -1 4
2 3 -1 -4
2 -3 1 4
2 -3 1 -4
2 -3 -1 4
2 -3 -1 -4
-2 3 1 4
-2 3 1 -4
-2 3 -1 4
-2 3 -1 -4
-2 -3 1 4
-2 -3 1 -4
-2 -3 -1 4
-2 -3 -1 -4
2 3 4 1
2 3 4 -1
2 3 -4 1
2 3 -4 -1
2 -3 4 1
2 -3 4 -1
2 -3 -4 1
2 -3 -4 -1
-2 3 4 1
-2 3 4 -1
-2 3 -4 1
-2 3 -4 -1
-2 -3 4 1
-2 -3 4 -1
-2 -3 -4 1
-2 -3 -4 -1
2 4 1 3
2 4 1 -3
2 4 -1 3
2 4 -1 -3
2 -4 1 3
2 -4 1 -3
2 -4 -1 3
2 -4 -1 -3
-2 4 1 3
-2 4 1 -3
-2 4 -1 3
-2 4 -1 -3
-2 -4 1 3
-2 -4 1 -3
-2 -4 -1 3
-2 -4 -1 -3
2 4 3 1
2 4 3 -1
2 4 -3 1
2 4 -3 -1
2 -4 3 1
2 -4 3 -1
2 -4 -3 1
2 -4 -3 -1
-2 4 3 1
-2 4 3 -1
-2 4 -3 1
-2 4 -3 -1
-2 -4 3 1
-2 -4 3 -1
-2 -4 -3 1
-2 -4 -3 -1
3 1 2 4
3 1 2 -4
3 1 -2 4
3 1 -2 -4
3 -1 2 4
3 -1 2 -4
3 -1 -2 4
3 -1 -2 -4
-3 1 2 4
-3 1 2 -4
-3 1 -2 4
-3 1 -2 -4
-3 -1 2 4
-3 -1 2 -4
-3 -1 -2 4
-3 -1 -2 -4
3 1 4 2
3 1 4 -2
3 1 -4 2
3 1 -4 -2
3 -1 4 2
3 -1 4 -2
3 -1 -4 2
3 -1 -4 -2
-3 1 4 2
-3 1 4 -2
-3 1 -4 2
-3 1 -4 -2
-3 -1 4 2
-3 -1 4 -2
-3 -1 -4 2
-3 -1 -4 -2
3 2 1 4
3 2 1 -4
3 2 -1 4
3 2 -1 -4
3 -2 1 4
3 -2 1 -4
3 -2 -1 4
3 -2 -1 -4
-3 2 1 4
-3 2 1 -4
-3 2 -1 4
-3 2 -1 -4
-3 -2 1 4
-3 -2 1 -4
-3 -2 -1 4
-3 -2 -1 -4
3 2 4 1
3 2 4 -1
3 2 -4 1
3 2 -4 -1
3 -2 4 1
3 -2 4 -1
3 -2 -4 1
3 -2 -4 -1
-3 2 4 1
-3 2 4 -1
-3 2 -4 1
-3 2 -4 -1
-3 -2 4 1
-3 -2 4 -1
-3 -2 -4 1
-3 -2 -4 -1
3 4 1 2
3 4 1 -2
3 4 -1 2
3 4 -1 -2
3 -4 1 2
3 -4 1 -2
3 -4 -1 2
3 -4 -1 -2
-3 4 1 2
-3 4 1 -2
-3 4 -1 2
-3 4 -1 -2
-3 -4 1 2
-3 -4 1 -2
-3 -4 -1 2
-3 -4 -1 -2
3 4 2 1
3 4 2 -1
3 4 -2 1
3 4 -2 -1
3 -4 2 1
3 -4 2 -1
3 -4 -2 1
3 -4 -2 -1
-3 4 2 1
-3 4 2 -1
-3 4 -2 1
-3 4 -2 -1
-3 -4 2 1
-3 -4 2 -1
-3 -4 -2 1
-3 -4 -2 -1
4 1 2 3
4 1 2 -3
4 1 -2 3
4 1 -2 -3
4 -1 2 3
4 -1 2 -3
4 -1 -2 3
4 -1 -2 -3
-4 1 2 3
-4 1 2 -3
-4 1 -2 3
-4 1 -2 -3
-4 -1 2 3
-4 -1 2 -3
-4 -1 -2 3
-4 -1 -2 -3
4 1 3 2
4 1 3 -2
4 1 -3 2
4 1 -3 -2
4 -1 3 2
4 -1 3 -2
4 -1 -3 2
4 -1 -3 -2
-4 1 3 2
-4 1 3 -2
-4 1 -3 2
-4 1 -3 -2
-4 -1 3 2
-4 -1 3 -2
-4 -1 -3 2
-4 -1 -3 -2
4 2 1 3
4 2 1 -3
4 2 -1 3
4 2 -1 -3
4 -2 1 3
4 -2 1 -3
4 -2 -1 3
4 -2 -1 -3
-4 2 1 3
-4 2 1 -3
-4 2 -1 3
-4 2 -1 -3
-4 -2 1 3
-4 -2 1 -3
-4 -2 -1 3
-4 -2 -1 -3
4 2 3 1
4 2 3 -1
4 2 -3 1
4 2 -3 -1
4 -2 3 1
4 -2 3 -1
4 -2 -3 1
4 -2 -3 -1
-4 2 3 1
-4 2 3 -1
-4 2 -3 1
-4 2 -3 -1
-4 -2 3 1
-4 -2 3 -1
-4 -2 -3 1
-4 -2 -3 -1
4 3 1 2
4 3 1 -2
4 3 -1 2
4 3 -1 -2
4 -3 1 2
4 -3 1 -2
4 -3 -1 2
4 -3 -1 -2
-4 3 1 2
-4 3 1 -2
-4 3 -1 2
-4 3 -1 -2
-4 -3 1 2
-4 -3 1 -2
-4 -3 -1 2
-4 -3 -1 -2
4 3 2 1
4 3 2 -1
4 3 -2 1
4 3 -2 -1
4 -3 2 1
4 -3 2 -1
4 -3 -2 1
4 -3 -2 -1
-4 3 2 1
-4 3 2 -1
-4 3 -2 1
-4 3 -2 -1
-4 -3 2 1
-4 -3 2 -1
-4 -3 -2 1
-4 -3 -2 -1

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)
#http://rosalind.info/problems/sign/

import itertools


def lettura(filename):
    with open(filename) as f:
         riga = f.readline()
         return int(riga)

def main():
    n = lettura("dataset.txt")
    soluzioni = []
    for p in itertools.permutations(range(1, n + 1)):
        for segni in itertools.product([1, -1], repeat=n):
            soluzioni.append([v * s for v, s in zip(p, segni)])
    print(len(soluzioni))
    for sol in soluzioni:
        print(" ".join(str(x) for x in sol))

if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente
// Enumerating Oriented Gene Orderings (Rosalind ID: SIGN) - soluzione
// JavaScript indipendente, non una trascrizione di problem.py: stessa
// logica (tutte le permutazioni di 1..n, ciascuna combinata con tutti i
// 2^n possibili segni), riscritta in modo idiomatico per JS.
//
// L'ordine di generazione riproduce esattamente quello di
// itertools.permutations(range(1, n+1)) (ordine lessicografico
// sull'iterabile ordinato) e di itertools.product([1, -1], repeat=n)
// (l'ultima posizione varia più velocemente).
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
function* permutazioni(elementi) {
  if (elementi.length === 0) {
    yield [];
    return;
  }
  for (let i = 0; i < elementi.length; i++) {
    const resto = [...elementi.slice(0, i), ...elementi.slice(i + 1)];
    for (const p of permutazioni(resto)) {
      yield [elementi[i], ...p];
    }
  }
}

function* combinazioniSegni(n) {
  if (n === 0) {
    yield [];
    return;
  }
  for (const segno of [1, -1]) {
    for (const resto of combinazioniSegni(n - 1)) {
      yield [segno, ...resto];
    }
  }
}

export default function solve(datasetText) {
  const riga = datasetText.split("\n")[0].trim();

  if (!/^\d+$/.test(riga)) {
    throw new Error(`Input non valido: atteso un intero, ricevuto "${riga}"`);
  }

  const n = Number(riga);
  const elementi = Array.from({ length: n }, (_, i) => i + 1);

  const soluzioni = [];
  for (const p of permutazioni(elementi)) {
    for (const segni of combinazioniSegni(n)) {
      soluzioni.push(p.map((v, i) => v * segni[i]));
    }
  }

  const righe = [String(soluzioni.length)];
  for (const sol of soluzioni) {
    righe.push(sol.join(" "));
  }

  return righe.join("\n") + "\n";
}