Indeks tablicy wielowymiarowej

28

Języki niższego poziomu, takie jak C i C ++, w rzeczywistości nie mają pojęcia tablic wielowymiarowych. (Inne niż wektory i tablice dynamiczne) Gdy tworzysz tablicę wielowymiarową za pomocą

int foo[5][10];

To właściwie tylko cukier syntaktyczny . To, co tak naprawdę robi C, to utworzenie pojedynczej ciągłej tablicy 5 * 10 elementów. To

foo[4][2]

jest także cukrem syntaktycznym. To naprawdę odnosi się do elementu w

4 * 10 + 2

lub 42 element. Ogólnie rzecz biorąc, indeks elementu [a][b]w tablicy foo[x][y]wynosi

a * y + b

Ta sama koncepcja dotyczy tablic 3d. Jeśli mamy foo[x][y][z]i uzyskujemy dostęp do elementu [a][b][c], to naprawdę uzyskujemy dostęp do elementu:

a * y * z + b * z + c

Ta koncepcja dotyczy tablic n- wymiarowych. Jeśli mamy tablicę z wymiarami D1, D2, D3 ... Dni uzyskujemy dostęp do elementu, S1, S2, S3 ... Snformuła jest następująca

(S1 * D2 * D3 ... * Dn) + (S2 * D3 * D4 ... * Dn) + (S3 * D4 ... * Dn) ... + (Sn-1 * Dn) + Sn

Wyzwanie

Musisz napisać program lub funkcję, która oblicza indeks tablicy wielowymiarowej zgodnie z powyższą formułą. Dane wejściowe będą mieć dwie tablice. Pierwsza tablica to wymiary, a druga tablica to indeksy. Długość tych dwóch tablic będzie zawsze równa i co najmniej 1.

Możesz bezpiecznie założyć, że każda liczba w tablicach będzie nieujemną liczbą całkowitą. Możesz również założyć, że nie dostaniesz się 0do tablicy wymiarów, chociaż 0 może być w indeksach. Możesz również założyć, że indeksy nie będą większe niż wymiary.

Przetestuj IO

Dimensions: [5, 10]
Indices: [4, 2]
Output: 42

Dimensions: [10, 10, 4, 62, 7]
Indices: [1, 2, 3, 4, 5]
Output: 22167

Dimensions: [5, 1, 10]
Indices: [3, 0, 7]
Output: 37

Dimensions: [6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
Indices: [3, 1, 5, 5, 3, 0, 5, 2, 5, 4]
Output: 33570178
DJMcMayhem
źródło
4
To jest indeksowanie oparte na 0, prawda? Czy możemy zastosować indeksowanie 1, jeśli jest to bardziej naturalne dla naszego wybranego języka?
Alex A.,
@AlexA. Tak, to jest do przyjęcia.
DJMcMayhem
11
Właściwie to, co C tak naprawdę robi, to utworzenie pojedynczej ciągłej tablicy pięciu elementów typu int[10].
Związane z.
Martin Ender,
1
@Hurkyl Tak, ale wszystkie liczby całkowite w tej tablicy są nadal ciągłe. To tylko semantyka.
DJMcMayhem

Odpowiedzi:

60

APL, 1 bajt

Przetestuj na TryAPL .

Dennis
źródło
21
Cóż, to wszystko. Mamy zwycięzcę. Wszyscy inni mogą teraz iść do domu.
DJMcMayhem
3
Dlaczego ... dlaczego to działa? o_O
Alex A.
10
@AlexA. Indeksowanie tablicy wielowymiarowej jest zasadniczo mieszaną konwersją bazy.
Dennis
21
Och, patrz, dziura w jednym podczas gry w golfa!
Pozew Fund Moniki w
8
Przez większość czasu przychodzę tu dla zabawy. Są chwile, kiedy przypadkowo otrzymuję głęboką wiedzę
slebetman
11

JavaScript (ES6), 34 bajty

(d,a)=>a.reduce((r,i,j)=>r*d[j]+i)

Z pewnością reducemusi być lepszy niż map.

Neil
źródło
7

Python, 43 bajty

f=lambda x,y:x>[]and y.pop()+x.pop()*f(x,y)

Przetestuj na Ideone .

Dennis
źródło
15
Dennis nie tylko solidnie nas wszystkich droczy, ale robi to w każdym. pojedynczy. język.
DJMcMayhem
7

Galaretka , 7 6 bajtów

Ṇ;żḅ@/

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Ṇ;żḅ@/  Main link. Arguments: D (list of dimensions), I (list of indices)

Ṇ       Yield 0, the logical NOT of D.
  ż     Zip D with I.
        If D = [10, 10, 4, 62, 7] and I = [1, 2, 3, 4, 5], this yields
        [[10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
 ;      Concatenate, yielding [0, [10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
   ḅ@/  Reduce by swapped base conversion to integer.
        [10, 1] in base    0 is    0 × 10 + 1 = 1.
        [10, 2] in base    1 is    1 × 10 + 2 = 12.
        [ 4, 3] in base   12 is   12 ×  4 + 3 = 51.
        [62, 4] in base   51 is   51 × 62 + 4 = 3166.
        [ 7, 5] in base 3166 is 3166 ×  7 + 5 = 22167.
Dennis
źródło
6

Pyth, 10 bajtów

e.b=+*ZNYC

Wypróbuj online: pakiet demonstracyjny lub testowy

Zastosowanie metody Hornera do obliczenia indeksu.

Jakube
źródło
5

MATL , 9 bajtów

PiPZ}N$X]

Wykorzystuje to indeksowanie 1 (teraz dozwolone przez wyzwanie), co jest naturalnym wyborem w MATL.

Aby porównać z przypadkami testowymi w wyzwaniu, dodaj 1do każdego wpisu w wektorze indeksu wejściowego i odejmij 1od wyniku.

Wypróbuj online!

Wyjaśnienie

Kod oparty jest na wbudowanej X]funkcji, która konwertuje wskaźniki wielowymiarowe na pojedynczy, liniowy indeks (taki jak sub2indfunkcja Matlaba lub Octave'a ).

P      % Take dimension vector implicitly. Reverse
iP     % Take vector of indices. Reverse
Z}     % Split vector into its elements
N$X]   % Convert indices to linear index (`sub2ind` function). Implicitly display
Luis Mendo
źródło
5

Julia, 29 27 bajtów

x%y=prod(x)÷cumprod(x)⋅y

Wypróbuj online!

Dennis
źródło
5

MATL , 11 bajtów

4L)1hPYpP*s

Korzysta z indeksowania opartego na 0, tak jak w oryginalnym wyzwaniu.

Wypróbuj online!

Wyjaśnienie

Kod wyraźnie wykonuje wymagane pomnożenia i uzupełnienia.

4L)    % Take first input array implicitly. Remove its first entry
1h     % Append a 1
PYpP   % Cumulative product from right to left
*      % Take second input array implicitly. Multiply the two arrays element-wise
s      % Sum of resulting array. Implicitly display
Luis Mendo
źródło
4

Python, 85 bajtów

lambda a,b:sum(b[i]*eval('*'.join(str(n)for n in a[i+1:])or'1')for i in range(len(a)))

Prawdopodobnie uda mi się skopać tyłek lepszym golfistom pythonowym.

DJMcMayhem
źródło
4

Python 3.5, 69

lambda d,i:sum(eval("*".join(map(str,[z,*d])))for z in i if d.pop(0))

Przetestuj tutaj

Alexander Nigl
źródło
Niezła odpowiedź! O wiele lepszy niż mój.
DJMcMayhem
@DrGreenEggsandHamDJ Ukradłem metodę eval z twojego rozwiązania :)
Alexander Nigl
4

Haskell, 34 bajty

a#b=sum$zipWith(*)(0:b)$scanr(*)1a

Przykład użycia: [10,10,4,62,7] # [1,2,3,4,5]-> 22167.

Jak to działa:

      scanr(*)1a  -- build partial products of the first parameter from the right,
                  -- starting with 1, e.g. [173600,17360,1736,434,7,1]
    (0:b)         -- prepend 0 to second parameter, e.g. [0,1,2,3,4,5]
  zipWith(*)      -- multiply both lists elementwise, e.g. [0,17360,3472,1302,28,5]
sum               -- calculate sum
nimi
źródło
4

C ++, 66 bajtów

Szybkie makro:

#include<stdio.h>
#define F(d,i) int x d;printf("%d",&x i-(int*)x)

Użyj jak:

int main(){
    F([5][1][10], [3][0][7]);
}

Może to być trochę nadużycie zasad. Tworzy tablicę o podanym rozmiarze, a następnie sprawdza, jak daleko dane indeksy przesunęły wskaźnik. Wyjścia do STDOUT.

To takie brudne ... Ale uwielbiam fakt, że to jest ważne.

MegaTom
źródło
3

Mathematica, 27 bajtów

#~FromDigits~MixedRadix@#2&

Nienazwana funkcja, która przyjmuje listę indeksów jako pierwszy argument, a listę wymiarów jako drugi. Bazując na tej samej obserwacji, co odpowiedź APL Dennisa, obliczenie indeksu jest tak naprawdę tylko konwersją o mieszanej podstawie.

Martin Ender
źródło
3

Oktawa, 58 54 bajtów

Dzięki @AlexA. za jego sugestię, która usunęła 4 bajty

@(d,i)reshape(1:prod(d),flip(d))(num2cell(flip(i)){:})

Wejścia i wyjścia są oparte na 1. Aby porównać z przypadkami testowymi, dodaj 1ot każdego wpisu na wejściu i odejmij 1od wyniku.

To anonimowa funkcja. Aby go wywołać, przypisz go do zmiennej.

Wypróbuj tutaj .

Wyjaśnienie

To działa przez rzeczywiście buduje wielowymiarowy array ( reshape(...)), wypełnioną wartościami 1, 2... w porządku liniowego ( 1:prod(d)), a następnie indeksowanie z indeksem wielowymiarowej uzyskać wartość corrresponding.

Indeksowanie odbywa się poprzez konwersję wejściowego indeksu wielowymiarowego ina tablicę komórek ( num2cell(...)), a następnie na listę oddzieloną przecinkami ( {:}).

Dwie flipoperacje są potrzebne do dostosowania kolejności wymiarów od C do Octave.

Luis Mendo
źródło
dlaczego przekształcenie ma drugą parę nawiasów, czy to nie jest składniowe?
Abr001am,
@ Agawa001 Czy masz na myśli drugą parę po reshape ? To nie jest składniowe w Matlabie, ale zaakceptowane w Octave. Działa jako indeks
Luis Mendo
oh Octave !! które muszą być lepsze i bardziej ergonomiczne niż oświecenie Matlab, Tha, Ks.
Abr001am,
@ Agawa001 Może to również prowadzić do pewnego zamieszania , choć
Luis Mendo
Wskazówka dotycząca anonimowych funkcji w przykładowym kodzie: używam @(...) ...w pierwszym wierszu mojego kodu, a następnie f = ans;w drugim. To sprawia, że ​​długość pierwszego wiersza jest równa liczbie bajtów do zgłoszenia.
bers
3

CJam, 7 bajtów

0q~z+:b

Wypróbuj online!

Jak to działa

0        e# Push 0 on the stack.
 q       e# Read and push all input, e.g., "[[10 10 4 62 7] [1 2 3 4 5]]".
  ~      e# Eval, pushing [[10 10 4 62 7] [1 2 3 4 5]].
   z     e# Zip, pushing [[10 1] [10 2] [4 3] [62 4] [7 5]].
    +    e# Concatenate, pushing [0 [10 1] [10 2] [4 3] [62 4] [7 5]]
     :b  e# Reduce by base conversion.
         e# [10 1] in base    0 is    0 * 10 + 1 = 1.
         e# [10 2] in base    1 is    1 * 10 + 2 = 12.
         e# [ 4 3] in base   12 is   12 *  4 + 3 = 51.
         e# [62 4] in base   51 is   51 * 62 + 4 = 3166.
         e# [ 7 5] in base 3166 is 3166 *  7 + 5 = 22167.
Dennis
źródło
Daj nam szansę, Dennis! : D
HyperNeutrino
2

Haskell, 47 bajtów

Dwa rozwiązania o równej długości:

s(a:b)(x:y)=a*product y:s b y
s _ _=[]
(sum.).s

Nazywane tak: ((sum.).s)[4,2][5,10].

Oto wersja poprawki:

(a:b)&(x:y)=a*product y:b&y
_ & _=[]
(sum.).(&)
Michael Klein
źródło
2

Oktawy, 47 / 43 /31 bajtów

@(d,i)sub2ind(flip(d),num2cell(flip(i+1)){:})-1

Sprawdź to tutaj .

Powiedziawszy to, zgodnie z pytaniem w komentarzu , indeksowanie 1 było powiedziane, że jest OK, gdy jest to naturalne dla używanego języka. W takim przypadku możemy zapisać 4 bajty:

@(d,i)sub2ind(flip(d),num2cell(flip(i)){:})

Analogicznie twierdzę, że jeśli celem kodu jest liniowe indeksowanie tablicy w tym języku , całe odwracanie i uwzględnianie głównego porządku kolumny MATLAB / Octave również nie powinno być konieczne. W takim przypadku moje rozwiązanie staje się

@(d,i)sub2ind(d,num2cell(i){:})

Przetestuj tutaj .

bers
źródło
Witaj i witaj w PPCG! Świetna odpowiedź!
NoOneIsHere
1

Mathematica, 47 bajtów

Fold[Last@#2#+First@#2&,First@#,Rest/@{##}]&

(Unicode to U + F3C7 lub \[Transpose].) W tym celu przepisałem wyrażenie jako D n ( D n -1 (⋯ ( D 3 ( D 2 S 1 + S 2 ) + S 3 ) ⋯) + S n -1 ) + S n . Jest tylko Foldfunkcja na obu listach.

LegionMammal978
źródło
1

Właściwie 13 bajtów

;pX╗lr`╜tπ`M*

Wypróbuj online!

Ten program przyjmuje listę wskaźników jako pierwsze dane wejściowe, a listę wymiarów jako drugie dane wejściowe.

Wyjaśnienie:

;pX╗lr`╜tπ`M*
;pX╗            push dims[1:] to reg0
    lr`   `M    map: for n in range(len(dims)):
       ╜tπ        push product of last n values in reg0
            *   dot product of indices and map result
Mego
źródło
1

Rakieta 76 bajtów

(λ(l i(s 0))(if(null? i)s(f(cdr l)(cdr i)(+ s(*(car i)(apply *(cdr l)))))))

Nie golfowany:

(define f
  (λ (ll il (sum 0))
    (if (null? il)
        sum
        (f (rest ll)
           (rest il)
           (+ sum
              (* (first il)
                 (apply * (rest ll))))))))

Testowanie:

(f '(5 10) '(4 2))
(f '(10 10 4 62 7) '(1 2 3 4 5))
(f '(5 1 10) '(3 0 7))

Wydajność:

42
22167
37
rnso
źródło
0

C #, 73 bajty

d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

Pełny program z przypadkami testowymi:

using System;

namespace IndexOfAMultidimensionalArray
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int[],Func<int[],int>>f= d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

            int[] dimensions, indices;
            dimensions =new int[]{5, 10};
            indices=new int[]{4,2};
            Console.WriteLine(f(dimensions)(indices));      //42

            dimensions=new int[]{10, 10, 4, 62, 7};
            indices=new int[]{1, 2, 3, 4, 5};
            Console.WriteLine(f(dimensions)(indices));      //22167

            dimensions=new int[]{5, 1, 10};
            indices=new int[]{3, 0, 7};
            Console.WriteLine(f(dimensions)(indices));      //37

            dimensions=new int[]{6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
            indices=new int[]{3, 1, 5, 5, 3, 0, 5, 2, 5, 4};
            Console.WriteLine(f(dimensions)(indices));      //33570178
        }
    }
}
adrianmp
źródło
0

Perl 6, 39 bajtów

->\d,\i{sum i.map:{[×] $_,|d[++$ ..*]}}

Raczej naiwny golf, po prostu zniszczył anonimowy okręt podwodny.

Perl 6 ma anonimową zmienną stanu, $która jest przydatna do tworzenia licznika w pętli (np. Przy użyciu przyrostu $++lub przyrostu ++$). Wstępnie zwiększam tę zmienną stanu, aby zwiększać indeks początkowy wycinka tablicy wymiarów wewnątrz mapy.

Oto niepoznana funkcja, która tworzy listy podrzędne

sub md-index(@dim, @idx) {
    @idx.map(-> $i { $i, |@dim[++$ .. *] })
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: ((1 10 4 62 7) (2 4 62 7) (3 62 7) (4 7) (5))

Następnie wystarczy ograniczyć listę podrzędną za pomocą ×operatora mnożenia ( ) i sumwprowadzić wyniki.

sub md-index(@dim, @idx) {
    @idx.map(-> $i { [×] $i, |@dim[++$ .. *] }).sum
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: 22167
Jozuego
źródło
0

Perl, 71 bajtów

sub{$s+=$_[1][-$_]*($p*=$_[0][1-$_])for($p=$_[0][$s=0]=1)..@{$_[0]};$s}

Nie golfowany:

sub {
    my $s = 0;
    my $p = 1;

    $_[0]->[0] = 1;
    for (1 .. @{$_[1]}) {
        $p *= $_[0]->[1 - $_];
        $s += $_[1]->[-$_] * $p;
    }

    return $s;
}
Denis Ibaev
źródło
0

C ++ 17, 133 115 bajtów

-18 bajtów do użycia auto...

template<int d,int ...D>struct M{int f(int s){return s;}int f(int s,auto...S){return(s*...*D)+M<D...>().f(S...);}};

Nie golfowany:

template <int d,int ...D> //extract first dimension
struct M{
 int f(int s){return s;} //base case for Sn
 int f(int s, auto... S) { //extract first index 
  return (s*...*D)+M<D...>().f(S...); 
  //S_i * D_(i+1) * D(i+2) * ... + recursive without first dimension and first index
 }
};

Stosowanie:

M<5,10>().f(4,2)
M<10,10,4,62,7>().f(1,2,3,4,5)

Alternatywnie, tylko funkcje, 116 bajtów

#define R return
#define A auto
A f(A d){R[](A s){R s;};}A f(A d,A...D){R[=](A s,A...S){R(s*...*D)+f(D...)(S...);};}

Nie golfowany:

auto f(auto d){
  return [](auto s){
   return s;
  };
}
auto f(auto d, auto...D){
  return [=](auto s, auto...S){
    return (s*...*D)+f(D...)(S...);
  };
}

Stosowanie:

f(5,10)(4,2)
f(10,10,10)(4,3,2)
f(10,10,4,62,7)(1,2,3,4,5)
Karl Napf
źródło